首先放上解法参考labuladong的团灭nsum
这里为大家讲解的是Python版本的代码，其实总体思路是一样的，只是我在解题的时候遇到了一些问题(放在本文最后)，觉得有必要和大家分享一下。
2 Sum
求list中和等于target的两个数，且不能重复。很自然想到对数组进行排序后采用双指针的方法求解：
(对应后面的求和题，我们在这里求具体的数，而不是index)
class soltuion:
def twoSum(self, nums, target):
nums.sort()
res = []
low, high = 0, len(nums) - 1
while low < high:
left, right = nums[low], nums[high]
tmp_sum = left + right
if tmp_sum > target:
# 只要nums[low]等于left，就会一直增加low，跳过这些重复的值
while low < high and nums[low] == left:
low += 1
elif tmp_sum < target:
# 只要nums[high]等于right，就会一直减少high，跳过这些重复的值
while low < high and nums[high] == right:
right -= 1
else:
res.append([left, right])
# 只要nums[low]等于left，就会一直增加low，跳过这些重复的值
while low < high and nums[low] == left:
low += 1
# 只要nums[high]等于right，就会一直减少high，跳过这些重复的值
while low < high and nums[high] == right:
hi -= 1
return res
有了2 Sum为基础，我们可以用它作为base case去求解3 Sum和4 Sum
3 Sum
求list中和等于target的两个数，且不能重复。使用2 Sum作为base case。
三数求和怎么转换成两数求和呢？很简单，遍历nums中的每一个数，将target减掉它，得到的值就可以作为2 Sum的target。
class soltuion:
def threeSum(self, nums, target):
nums.sort()
res = []
l = len(nums)
i = 0
# 这里用i<l-1，是因为留出一个加1的位置给twoSum
# 反正twoSum里面也要判断边界条件，所以就不在这里判断了
while i < l-1:
# 减掉当前数，用2 Sum去寻找剩下的值
base_cases = self.twoSum(nums, i+1, target-nums[i])
for x in base_cases:
res.append([nums[i] + x])
# 道理同上，跳过重复的值，剩下区间的重复值在twoSum里会检查
while i < l-1 and nums[i] == nums[i+1]:
i += 1
i += 1
return res
# 代码基本同上，除了多了一个start来指示low
def twoSum(self, nums, start, target):
res = []
low, high = start, len(nums) - 1
while low < high:
left, right = nums[low], nums[high]
tmp_sum = left + right
if tmp_sum < target:
while low < high and nums[low] == left:
low += 1
elif tmp_sum > target:
while low < high and nums[high] == right:
right -= 1
else:
res.append(left, right)
while low < high and nums[low] == left:
low += 1
while low < high and nums[high] == right:
right -= 1
return res
好了，想必你已经猜到怎么去求解4 Sum了。没错，就是将它转换成3 Sum，再由3 Sum转换成2 Sum，一级一级地调用。
4 Sum
class soltuion:
def fourSum(self, nums, target):
nums.sort()
res = []
l = len(nums)
i = 0
# 这里用i<l-1，是因为留出一个加1的位置给twoSum
# 反正twoSum里面也要判断边界条件，所以就不在这里判断了
while i < l-1:
# 减掉当前数，用3 Sum去寻找剩下的值
base_cases = self.threeSum(nums, i+1, target-nums[i])
for x in base_cases:
res.append([nums[i] + x])
# 道理同上，跳过重复的值，剩下区间的重复值在twoSum里会检查
while i < l-1 and nums[i] == nums[i+1]:
i += 1
i += 1
return res
def threeSum(self, nums,start, target):
nums.sort()
res = []
l = len(nums)
# 3 Sum的起始从4 Sum的下一个数开始
i = start
while i < l-1:
# 减掉当前数，用2 Sum去寻找剩下的值
base_cases = self.twoSum(nums, i+1, target-nums[i])
for x in base_cases:
res.append([nums[i] + x])
# 道理同上，跳过重复的值，剩下区间的重复值在twoSum里会检查
while i < l-1 and nums[i] == nums[i+1]:
i += 1
i += 1
return res
# 代码基本同上，除了多了一个start来指示low
def twoSum(self, nums, start, target):
res = []
low, high = start, len(nums) - 1
while low < high:
left, right = nums[low], nums[high]
tmp_sum = left + right
if tmp_sum < target:
while low < high and nums[low] == left:
low += 1
elif tmp_sum > target:
while low < high and nums[high] == right:
right -= 1
else:
res.append(left, right)
while low < high and nums[low] == left:
low += 1
while low < high and nums[high] == right:
right -= 1
return res
最后，我来讲讲自己解题时遇到的“麻烦”*。(提示：如果你知道Python里for i in range(x)的坑，请无视以下部分)
请先看出现在4 Sum和3 Sum里的一部分代码：
while i < l-1:
# 减掉当前数，用3 Sum去寻找剩下的值
base_cases = self.threeSum(nums, i+1, target-nums[i])
for x in base_cases:
res.append([nums[i] + x])
# 道理同上，跳过重复的值，剩下区间的重复值在twoSum里会检查
while i < l-1 and nums[i] == nums[i+1]:
i += 1
i += 1
我在一开始的时候，并不是用的"while i < l-1"，而是用的"for i in range(l)"。乍一看，好像两者没什么区别，用了for循环就不需要在最后写"i += 1"了。可是，提交的结果就是有重复的。于是，我自己写了一个小的测试代码：
a = 10
for i in range(a):
print(i)
while i % 2 == 0:
i += 1
print(i)
print(i)
print('####')
结果如下：
0
1
1
####
1
1
####
2
3
3
####
3
3
####
...
也就是说，不管我在for循环里面怎么修改i的值，进行下一轮循环的时候i还是去range这个可迭代对象里取下一个i值。所以我用for循环+range会产生重复的结果，找到原因后，就改写为了while循环。
希望这个解释能帮助到你：）
网友评论