链接

难度

描述

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 >  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 >  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  

class Solution:

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        nums = sorted(nums)
        ret = []
        i, j = , 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