18. 四数之和

题目链接：国际版，国内版
公司：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 < n
• a, 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)