四数之和

难度: Medium

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

Submission

运行时间: 1324 ms

内存: 15.3 MB

from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def nSum(n, start, tar):
            res = []
            if n == 2:
                i = start
                j = len(nums)-1
                while i < j:
                    s = nums[i] + nums[j]
                    left = nums[i]
                    right = nums[j]
                    if s < tar:
                        while i < j and nums[i] == left:
                            i += 1
                    elif s > tar:
                        while i < j and nums[j] == right:
                            j -= 1
                    else:
                        print(left, right)
                        res.append([left, right])
                        while i < j and nums[i] == left:
                            i += 1
                        while i < j and nums[j] == right:
                            j -= 1
            elif n > 2:
                i = start
                while i < len(nums):
                    tuples = nSum(n-1, i+1, tar-nums[i])
                    for t in tuples:
                        t.append(nums[i])
                        res.append(t)
                    while i+1 < len(nums) and nums[i+1] == nums[i]:
                        i += 1
                    i += 1
            return res

        nums.sort()
        return nSum(4, 0, target)


if __name__ == '__main__':
    s = Solution()
    print(s.fourSum([-2,-1,-1,1,1,2,2], 4))

Explain

这道题目使用了nSum的递归思想来解决。首先将数组排序，然后递归地调用nSum函数，将问题不断分解成更小的子问题，直到问题简化为两数之和。在两数之和的处理中，使用双指针技巧来寻找和为目标值的元素对。为了避免重复解，每次找到一个解后，需要跳过相同的元素。

时间复杂度: O(n^3)

空间复杂度: O(n^3)

from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def nSum(n, start, tar):
            res = []
            if n == 2:
                i = start
                j = len(nums)-1
                while i < j:
                    s = nums[i] + nums[j]
                    left = nums[i]
                    right = nums[j]
                    if s < tar:
                        while i < j and nums[i] == left:
                            i += 1
                    elif s > tar:
                        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
            elif n > 2:
                i = start
                while i < len(nums):
                    tuples = nSum(n-1, i+1, tar-nums[i])
                    for t in tuples:
                        t.append(nums[i])
                        res.append(t)
                    while i+1 < len(nums) and nums[i+1] == nums[i]:
                        i += 1
                    i += 1
            return res

        nums.sort()
        return nSum(4, 0, target)


if __name__ == '__main__':
    s = Solution()
    print(s.fourSum([-2,-1,-1,1,1,2,2], 4))

Explore

在排序数组中，使用双指针方法可以更直观且高效地找到和为目标值的两个数。使用双指针时，可以有效地利用数组的有序性，通过移动左右指针以逼近目标值，从而避免额外的空间复杂度。而使用哈希表虽然能在未排序的情况下快速查找元素，但它需要额外的空间来存储元素和它们的索引，且在处理重复元素和保持结果的有序性方面更加复杂。

为了确保不出现重复的四元组，算法在每次找到有效的子问题解后，会跳过所有与当前元素相同的后续元素。这是通过在递归的每一层中，在处理完当前元素并找到所有相关的子问题解之后，检查后续元素是否与当前元素相同来实现的。如果相同，就继续跳过，直到找到一个不同的元素或者数组结束。这种方法确保每个数字在每个位置只被使用一次，从而避免生成重复的组合。

递归地将nSum问题递减至n-1是为了简化问题的复杂性，同时保持问题的结构清晰和可控。通过逐步递减，可以将n数之和的问题逐步分解为更易于解决的子问题，最终简化到两数之和，这是一个直接可以通过双指针高效解决的问题。如果直接跳过n-1到更小的数，比如n-2，虽然理论上可行，但在实践中会使问题的分解和解决变得复杂，需要更多的递归层次和复杂的中间状态管理。