LeetCode 18： 4 Sum 寻找4数和
- 2020 年 3 月 5 日
- 筆記
点击上方蓝字，和我一起学技术。
链接
https://leetcode.com/problems/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的情况下，只要稍稍修改一点点，代码就可以投入使用了。但是这并不是最佳方案，我们来计算一下复杂度。
首先，我们枚举了第一个元素，它的复杂度是。另外，3 Sum的复杂度是。所以整体上，这是一个的复杂度，虽然从问题层面来思考，要比的暴力枚举提升了一个层次，但是看起来应该还有进化的空间。那么怎么进化呢？
一个想法是我们能不能跳过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，但实际上，我们最外层并没有办法做到的枚举。因为我们无法同时缩放两个区间，看起来是两个two pointers套用，但实际上还是只是用到了一个two pointers算法而已。我们最外层的遍历，相当于枚举了内层two pointers算法作用的区间。这个枚举是的复杂度，整体的复杂度同样是和使用3 Sum的一样。
但这不意味着我们讨论这种解法就没有意义了，相反，对于算法学习而言，比解出问题更重要的是对于问题充分的思考。虽然从表面上看我们费心想出来的另一种方案并没有得到提升，但是相比于提升而言，我们在此过程当中经历了充分的思考，无论是分析可行性还是最后分析复杂度，莫不如此。正是在反复的思考当中，我们的算法思维才能养成，解题能力才能提升。
当然，另一个原因是不掰扯出一些道理来，这么大段我就白写了【狗头】。
今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
