题目链接：国际版，国内版
公司：Meta
解法：双指针、递归
题目描述
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na, b, c, and d are distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
思路
如果你已经做过 2sum 和 3sum 了，那么这道题的题目描述你应该已经很熟悉了，即：在一个无序且有重复的数组中找到四个元素，使它们的和为 0，返回所有可能的结果。看到这里，我们首先先来回忆一下 3sum 的解法，即：将数组排好序，每次固定一个元素 nums[i]，再在剩余的子数组 nums[i+1:] 中找 2sum 结果为 target - nums[i] 的两个元素即可。那么以此类推，对于这道 4sum，我们也可以将数组排好序之后固定一个元素，在剩下的数组元素中找 3sum。这种思路的参考代码如下：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
""" 固定住第一个元素，对后续元素进行threeSum，注意去重 """
def three_sum(nums, start, target):
def two_sum(numbers, start_idx, target):
res = []
i, j = start_idx, len(numbers) - 1
while i < j:
tmp = numbers[i] + numbers[j]
left, right = numbers[i], numbers[j]
if tmp < target:
while i < j and numbers[i] == left: i += 1
elif tmp > target:
while i < j and numbers[j] == right: j -= 1
else:
res.append([i, j])
while i < j and numbers[i] == left: i += 1
while i < j and numbers[j] == right: j -= 1
return res
res = []
i = start
while i < len(nums):
tuples = two_sum(nums, i + 1, target - nums[i])
for j, k in tuples:
res.append([i, j, k])
while i < len(nums) - 1 and nums[i + 1] == nums[i]:
i += 1
i += 1
return res
nums.sort()
res = []
a = 0
while a < len(nums):
tuples = three_sum(nums, a + 1, target - nums[a])
for b, c, d in tuples:
res.append([nums[a], nums[b], nums[c], nums[d]])
while a < len(nums) - 1 and nums[a + 1] == nums[a]:
a += 1
a += 1
return res
这种解法可以解题，但存在一个问题，即：如果面试的时候面试官问你 5sum、6sum 怎么写，难道我们还能从 2sum 开始一层一层地写下去么？为此我们再次观察一下思路：求 4sum 我们需要知道 3sum，求解 3sum 我们需要知道 2sum，求解 2sum 就可以直接在 O(N) 的时间内算出来了。因此，求解 nSum 问题，我们需要知道 (n-1)Sum 的解，这就变成了一个递归的解法。同时，递归的终止条件是 2sum。参考代码如下：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
"""通用解法"""
def nSum(nums, n, start, target):
res = []
if n < 2:
return res
if n == 2:
i, j = start, len(nums) - 1
while i < j:
curr = nums[i] + nums[j]
left, right = nums[i], nums[j]
if curr < target:
# 去重
while i < j and nums[i] == left:
i += 1
elif curr > target:
# 去重
while i < j and nums[j] == right:
j -= 1
else:
res.append([left, right])
# 去重
while i < j and nums[i] == left:
i += 1
while i < j and nums[j] == right:
j -= 1
return res
else:
i = start
while i < len(nums):
tmp = nSum(nums, n - 1, i + 1, target - nums[i])
for tmp_res in tmp:
tmp_res.append(nums[i])
res.append(tmp_res)
# 去重
while i < len(nums) - 1 and nums[i + 1] == nums[i]:
i += 1
i += 1
return res
nums.sort()
return nSum(nums, 4, 0, target)
我们这里定义了一个名为 nSum 的 helper function，它的作用就是对于给定的数组，从中找出 n 个数，使其和为 target。退出条件如之前所述，是 n == 2 的时候，就演变为了 2sum。当 n > 2 的时候，我们每次需要固定一个元素，再在剩下的元素中寻找 (n-1)sum。对于返回的每一个可能的组合，我们将其拼装成最后的结果，即在列表中加上所固定的那个元素即可。
对于时间复杂度分析，我们需要看递归树的深度。假设数组长度为 N，我们要求 k sum，由于递归退出的条件是 k = 2，因此总的递归树深度应该为 k - 1，时间复杂度应该为 O(N^(k-1))。对于空间复杂度分析，我们主要考虑递归需要的栈的空间。由于递归树深度为 k -1，因此栈的空间复杂度应该为 O(k-1)，在最坏情况下 k 应该等于 n，则空间复杂度为 O(N)
