实战 LeetCode 15.三数之和、18.四数之和，并扩展至 N 数之和
实战 LeetCode 15.三数之和、18.四数之和，并扩展至 N 数之和
题目描述
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/
如果有其他问题的话，可以在公众号底部找到我的联系方式，一起交流。