LeetCode 18： 4 Sum 寻找4数和

链接

4Sum

难度

Medium

描述

Given an array nums of n integers and an integer target, are there elements a , b , c , and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

给定一个n个整数的数组n，和一个整数target，要求在数组当中找到所有四个数和等于targe的组合。返回所有不重复的组合。

注意:

The solution set must not contain duplicate quadruplets.

答案当中不能包含重复的组合

样例:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

题解

这题是上周的3 Sum的进化版，要说这出题人也是够偷懒的，同样的题目稍微换一个条件就是新的题目了。要这样出题的话，我们分分钟可以出个十来题。

暴力

LeetCode当中的题目就没有几道是一次暴力无法解决的，如果有，就暴力两次。——承志。

显然，这题让我们寻找4个数的组合，满足它们的和等于target。这简直没有更明显的暴力暗示了，暗示我们可以暴力来解决，并且暴力的方法非常明确，暴力的代码非常简短。

我们直接跳过解释部分，来写下代码：

def 4Sum(array):
    n = len(array)
    ret = []
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                for l in range(k+1, n):
                    if array[i] + array[j] + array[k] + array[l] == target:
                        if [array[i], array[j], array[k], array[l]] not in ret:
                            ret.append([array[i], array[j], array[k], array[l]])
    return ret

显然，暴力法不是最好的，是最差的，不然也不用给大家写这篇文章了。

我们前面吐槽说这题和上周做的3 Sum题如出一辙，那么能否利用3 Sum的算法来完成4 Sum呢？毕竟这两题除了条件有细微的不同，大致题面完全相同。

如果我们真这么去想，又会有一个新的槽点：既然4 Sum可以用3 Sum来解决，然而我们又都知道3 Sum的解法之一是通过2 Sum，所以这不成了套娃问题了么？【狗头】

使用3 Sum

言归正传，回到算法本身，在3 Sum问题当中，我们通过two pointers算法，维护了一个区间，使得这个区间头尾元素的和等于一个特定值。所以我们利用3 Sum也一样，我们只需要枚举第一个元素，然后在剩下的数组当中，套用3 Sum寻找可能的组合即可。

解法也很简单，我们只需要把之前3 Sum的代码抄过来，然后增加一个调用函数即可。

class Solution:

    def three_sum(self, array, aim):
        # 无须排序，因为传入的时候已经有序了
        n = len(array)
        ret = []
        for i in range(n-2):
            # 判断第一个数是否重复
            if i > 0 and array[i] == array[i-1]:
                continue
            # 进行two pointers缩放
            j = i + 1
            k = n - 1
            target = aim - array[i]
            while j < k:
                cur_sum = array[j] + array[k]
                # 判断当前区间的结果和目标的大小
                if cur_sum < target:    
                    j += 1
                    continue
                elif cur_sum > target:
                    k -= 1
                    continue
                # 记录
                answer = [array[i], array[j], array[k]]
                ret.append(answer)
                # 继续缩放区间，寻找其他可能的答案
                j += 1
                while j < k and array[j] == array[j-1]:
                    j += 1
                k -= 1
                while j < k-1 and array[k] == array[k+1]:
                    k -= 1
        return ret

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        # 对数组进行排序
        nums = sorted(nums)
        ret = []
        for i in range(n):
            # 枚举第一个元素重复的话需要跳过
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 获取3 Sum的结果
            # 由于3 Sum当中做了防止重复的判断，所以不需要判断重复
            sub_ret = self.three_sum(nums[i+1: ], target - nums[i])
            for subset in sub_ret:
                ret.append([nums[i]] + subset)
        return ret

双重two pointers

上面的算法固然可以，尤其是我们之前做了3 Sum的情况下，只要稍稍修改一点点，代码就可以投入使用了。但是这并不是最佳方案，我们来计算一下复杂度。

首先，我们枚举了第一个元素，它的复杂度是 $O(n)$ 。另外，3 Sum的复杂度是 $O(n^2)$ 。所以整体上，这是一个 $O(n^3)$ 的复杂度，虽然从问题层面来思考，要比 $O(n^4)$ 的暴力枚举提升了一个层次，但是看起来应该还有进化的空间。那么怎么进化呢？

一个想法是我们能不能跳过3 Sum直接用2 Sum？其实可以的，因为我们在3 Sum当中只枚举了第一个数，然后通过two pointers寻找剩下的两个数的组合。所以我们可以使用一次two pointers然后剩下的元素做2 Sum，但是仔细一想，既然我们已经用了一次two pointers了，为什么不做两次呢？虽然复杂度是一样的，但是可以减少map的使用。

想明白了，算法也就出来了。说白了就是套用两次two pointers。最外层的two pointers算法枚举两个数的和，中间的two pointers算法寻找剩下的两个数。

光凭脑子想可能还有些发蒙，我列出代码，我们结合代码一起看就清楚了。

class Solution:

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        nums = sorted(nums)
        ret = []
        i, j = 0, n-1
        while i < j-2:
            while j > i+2:
                # two pointers算法
                l, r = i+1, j-1
                tar = target - nums[i] - nums[j]
                while l < r:
                    if nums[l] + nums[r] < tar:
                        l += 1
                    elif nums[l] + nums[r] > tar:
                        r -= 1
                    else:
                        ret.append([nums[i], nums[l], nums[r], nums[j]])
                        l += 1
                        r -= 1
                        # 跳过l和r的重复元素
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                        while l < r and nums[r] == nums[r+1]:
                            r -= 1
                # 跳过j的重复元素
                j -= 1
                while j > i+2 and nums[j] == nums[j+1]:
                    j -= 1
            # 对于新的i，j重新置为末尾
            j = n-1
            # 跳过i重复的元素
            i += 1
            while i+2 < j and nums[i] == nums[i-1]:
                i += 1
        return ret

我们结合代码来看，虽然我们使用了两套two pointers，但实际上，我们最外层并没有办法做到 $O(n)$ 的枚举。因为我们无法同时缩放两个区间，看起来是两个two pointers套用，但实际上还是只是用到了一个two pointers算法而已。我们最外层的遍历，相当于枚举了内层two pointers算法作用的区间。这个枚举是 $O(n^2)$ 的复杂度，整体的复杂度同样是 $O(n^3)$ 和使用3 Sum的一样。

但这不意味着我们讨论这种解法就没有意义了，相反，对于算法学习而言，比解出问题更重要的是对于问题充分的思考。虽然从表面上看我们费心想出来的另一种方案并没有得到提升，但是相比于提升而言，我们在此过程当中经历了充分的思考，无论是分析可行性还是最后分析复杂度，无比如此。正是在反复的思考当中，我们的算法思维才能养成，解题能力才能提升。

当然，另一个原因是不掰扯出一些道理来，这么大段话我就白写了。

今天的文章到这里就结束了，如果喜欢本文的话，请来一波素质三连，给我一点支持吧（关注、在看、点赞）。