提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
提示：类似的一些列题解法，有两数之和，三数之和，四数之和等，这一次记录的是各种适合使用指针来做题接的方法，。博主之前不死心，秉着万物皆可递归的想法，把自己搞的欲生欲四，虽然递归加DFS的方法真的很爽，但是剪枝这个方法还需要多修炼。
题目描述:给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 示例：给定 nums = [2, 7, 11, 15], target = 9。因为 nums[0] + nums[1] = 2 + 7 = 9。所以返回 [0, 1]
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: l=len(nums) if not l: return [] nums,ind=zip(*sorted(zip(nums,list(range(l))))) # 使用zip函数，设置辅助队列ind,队列里的值是nums对应的下标 i=0 j=l-1 while i<j: if nums[i]+nums[j]==target: return [ind[i],ind[j]] elif nums[i]+nums[j]>target: j-=1 else: i+=1 return []给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [[-1, 0, 1], [-1, -1, 2]]
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: # 思路解析 # 对于传入的数组 nums, 三数之和 # 1，只要数组内的数小于3 或等于0，则返回false # 2, 对数组进行初步排序 # 3，排序后判断第一个数的大小， 是否小于0，否则后面将不会有小于0的值，则直接返回false # 4,对于重复的数， 直接跳过 # 5，设置左指针和右指针， L = i+1， R = N-1 # 6，遍历排序后的数组，一旦找到 s = nums[i] + nums[L+1] + nums[N-1] = 0,将这和组合加入到res队列中去 # 再判断左右边界是否出现重复的情况。 # 7，最后判断 s 小于0,则值小了，左进一位，L=L+1， 若大于0 ,则是大了，右减一位 n = len(nums) res = [] if (not nums or n<3): return [] nums.sort() for i in range(n): if (nums[i]>0): # 判断排序后的第一个数的大小，因为target是0,若都一个大于0,就不可能找到三数之和为0 return res if (i>0 and nums[i] == nums[i-1]): #去重，为了避免出现重复的三元组。同一层下避免同一个序列出现多次 continue L = i+1 R = n-1 while(L<R): if(nums[i]+nums[L]+nums[R] == 0): # 设置返回条件，一旦找到三数之和为0的情况，返回序列 res.append([nums[i],nums[L],nums[R]]) while(L<R and nums[L] == nums[L+1]): #当重复元素出现时，跳过当前的L,指向L+1 L=L+1 while(L<R and nums[R] == nums[R-1]): #当重复元素出现时，跳过当前的R,指向R-1 R=R-1 L= L+1 R= R-1 elif(nums[i]+nums[L]+nums[R]>0): # 相加大于0，数大了， R-1 R=R-1 else: # 相加小于0，数小了， L+1 L=L+1 return res第二种解法：泛用于N数之和,使用回溯剪枝的思路。 关键点是:
先对nums排序；递归处理时的剪枝处理(参考注释) 这种写法参考了国际站上的文章，我觉得是最好的一种解法了。 class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: if not nums: return [] # 先排序，关键！ nums.sort() ans = set() N, target = 3, 0 self._find_sum(nums, 0, N, target, [], ans) return list(ans) def _find_sum(self, nums, start, N, target, path, ans): # terminator if len(nums) < N or N < 2: return # process if N == 2: # 两数求和 d = set() for j in range(start, len(nums)): if target - nums[j] in d: ans.add(tuple(path + [target - nums[j], nums[j]])) else: d.add(nums[j]) else: for i in range(start, len(nums)): # 剪枝1: target比剩余数字能组成的最小值还要小 或 比能组成的最大值还要大，就可以停止循环了 if target < nums[i] * N or target > nums[-1] * N: break # 剪枝2: 去重 if i > start and nums[i] == nums[i - 1]: continue # drill down self._find_sum(nums, i + 1, N - 1, target - nums[i], path + [nums[i]], ans) return提示：这里对文章进行总结： 例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。
