给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
题意分析：
从数组中4个数，使其和为target，找出所有可能
思路分析：
思路同3Sum，3Sum Closest。如果本身还不知道3Sum的思路可以参考这篇博客
当然即使你不知道也可以先往下看！
首先对数组排序，这是通用的处理方式。
在3Sum问题中，我们选择固定住第一个数nums[i]，然后问题就转换成在剩下的数组中找2个数，使其和为target-num[i]，即twoSum()问题
而2Sum问题我们可以用双指针法解决！！！
那么在4Sum问题，我们也可以采用同样的方式，固定住一个数，问题转换成3Sum问题，再固定一个数，问题转换成2Sum问题。然后使用双指针法解决。
以此类推，如果碰到NSum问题呢，我们就固定N-2个数，然后用双指针法解决。复杂度为O(n^(N-1))
还是按照惯例，我们先来写twoSum()函数，默认nums有序1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def twoSum(nums, target):
n = len(nums)
i, j = 0, n-1
res = []
while i < j:
if nums[i] + nums[j] == target:
res.append([nums[i], nums[j]])
i += 1; j -= 1
elif nums[i] + nums[j] < target:
i += 1
else:
j -= 1
# 因为要避免重复情况，所以这里要跳过若干数
while j > i > 0 and nums[i] == nums[i-1]: i += 1
while n-1 > j > i and nums[j] == nums[j+1]: j -= 1
return res
那么，fourSum()函数也可写1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35# 88ms, beats 81.04%
class Solution(object):
def twoSum(self, nums, target):
n = len(nums)
i, j = 0, n-1
res = []
while i < j:
if nums[i] + nums[j] == target:
res.append([nums[i], nums[j]])
i += 1; j -= 1
elif nums[i] + nums[j] < target:
i += 1
else:
j -= 1
while j > i > 0 and nums[i] == nums[i-1]: i += 1
while n-1 > j > i and nums[j] == nums[j+1]: j -= 1
return res
def fourSum(self, nums, target):
nums.sort()
n = len(nums)
res = []
for i in range(n-3):
if i > 0 and nums[i] == nums[i-1]: continue
for j in range(i+1,n-2):
if j > i+1 and nums[j] == nums[j-1]: continue
# 类似3Sum Closest，当最小都比target大或最大都比target小就跳过
if nums[i]+nums[j]+nums[j+1]+nums[j+2] > target: break
if nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target: break
# 用twoSum得出结果
rec = self.twoSum(nums[j+1:], target-nums[i]-nums[j])
if not rec: continue
for info in rec:
res.append([nums[i],nums[j]] + info)
return res