题目描述
15.三数之和
链接：https://leetcode-cn.com/problems/3sum/
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
18.四数之和
链接：https://leetcode-cn.com/problems/4sum/
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
其实这两道题前面还有一道更加基础的题，那就是第一题，两数之和。
因为题目比较简单，而且我觉得大部分人也应该都知道这道题，所以这里就不再贴第一题了。
不过这几道题都很经典，面试的时候会被经常问道。
这几道题也都不难，但是有一定的技巧在里面。掌握了不仅有助于拓展思维，而且对于面试求职也有很大帮助。
题目分析
做这类题的话，如果之前没有见过的话，很大可能就只能选择暴力求解了。不是说这样做不行，实在想不到其他方法了，也可以。
但是这类题目还有一种解法，叫做双指针，说实话，我刚开始做的时候也是完全不懂，但是自己做完后查看别人写的优秀代码后，发现双指针不仅代码优雅，而且非常高效。
就拿三数之和来说，如果按照暴力来进行求解的话，需要设置三层循环，但是双指针解法可以减少一层循环。
具体的代码如下：
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: ans = [] if len(nums) < 3: return ans nums.sort() for i in range(len(nums)-2): # 如果最小的三个数已经大于 0，退出程序 if nums[i] + nums[i+1] + nums[i+2] > 0: break # 如果最大的三个数还小于0，continue if nums[i] + nums[-1] + nums[-2] < 0: continue # 如果当前这个数等于前一个数， continue if i > 0 and nums[i] == nums[i-1]: continue # 双指针 left, right = i + 1, len(nums) - 1 while left < right: three_sum = nums[i] + nums[left] + nums[right] # 如果三数之和等于 0， if three_sum == 0: ans.append([nums[i], nums[left], nums[right]]) # 去除重复的左边元素 while left < right and nums[left] == nums[left+1]: left += 1 # 去除重复的右边元素 while left < right and nums[right] == nums[right-1]: right -= 1 # 更新 left， right的值 left += 1 right -= 1 # 如果三数之和小于 0 elif three_sum < 0: left += 1 # 如果三数之和大于 0 else: right -= 1 return ans
复制代码
看懂了三数之和，四数之和就和三数之和一样了。
代码如下：
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: ans = [] if len(nums) < 4: return ans; nums.sort() length = len(nums) for i in range(length): if nums[i] > 0 and target < 0: break if i > 0 and nums[i] == nums[i-1]: continue for j in range(i+1, length): if j > i+1 and nums[j] == nums[j-1]: continue two_sum = nums[i] + nums[j] if two_sum > 0 and target < 0: break left, right = j + 1, length - 1 while left < right: four_sum = two_sum + nums[left] + nums[right] # residual = target - nums[i] - nums[j] - nums[left] - nums[right] if four_sum == target: ans.append([nums[i], nums[j], nums[left], nums[right]]) while left < right and nums[left] == nums[left+1]: left += 1 while left < right and nums[right] == nums[right-1]: right -= 1 left += 1 right -= 1 elif four_sum < target: left += 1 else: right -= 1 return ans
复制代码
延伸
有了三数之和、四数之和，那么接下来还有五数之和,以及 N 数之和...,那么有没有一种通用的方法呢？
当前的方法也可以，不过需要事先确定 N，如果 N 不确定的话，就没办法了。
这个时候递归就派上用场了，而且同样可以使用双指针。
具体实现看代码：
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: def nSum(nums: List[int], n: int, target: int) -> List[List[int]]: res = [] if len(nums) < n: return res if n == 2: left, right = 0, len(nums) - 1 while left < right: if nums[left] + nums[right] == target: res.append([nums[left], nums[right]]) while left < right and nums[left] == nums[left+1]: left += 1 while left < right and nums[right] == nums[right-1]: right -= 1 left += 1 right -= 1 elif nums[left] + nums[right] < target: left += 1 else: right -= 1 return res else: for i in range(len(nums)-n+1): if i > 0 and nums[i] == nums[i-1]: continue min_sum = sum(nums[i:i+n]) if min_sum > target: break max_sum = nums[i] + sum(nums[-n+1:]) if max_sum < target: continue sub_res = nSum(nums[i+1:], n-1, target-nums[i]) for j in range(len(sub_res)): res.append([nums[i]]+sub_res[j]) return res nums.sort() res = nSum(nums, 3, 0) return res
复制代码
对于四数之和的话，将对应的参数修改下，就可以了。
总结
双指针是比较经典的一种方法，使用得当的话不仅可以写出优雅的代码，而且效率也很高。
如果觉得自己已经理解了的话，可以去 LeetCode 上实际写下。看看自己到底有没有掌握。
LeetCode 上更多的关于双指针的题目链接：
https://leetcode-cn.com/tag/two-pointers/
如果有其他问题的话，欢迎评论交流。
另外，欢迎关注我的微信公 &&众 &&号 「与你一起学算法」，领取刷题福利。
评论