18. 四数之和-python刷题-灵神

题目描述

思路讲解

思路和 15. 三数之和 一样，排序后，枚举 nums[a] 作为第一个数，枚举 nums[b] 作为第二个数，那么问题变成找到另外两个数，使得这四个数的和等于 target，这可以用双指针解决。

优化思路也和视频中讲的一样，对于 nums[a] 的枚举：

1. 设 s = nums[a] + nums[a+1] + nums[a+2] + nums[a+3]。如果 s > target，由于数组已经排序，后面无论怎么选，选出的四个数的和不会比 s 还小，所以后面不会找到等于 target 的四数之和了。所以只要 s > target，就可以直接 break 外层循环了。

2. 设 s = nums[a] + nums[n−3] + nums[n−2] + nums[n−1]。如果 s < target，由于数组已经排序，nums[a] 加上后面任意三个数都不会超过 s，所以无法在后面找到另外三个数与 nums[a] 相加等于 target。但是后面还有更大的 nums[a]，可能出现四数之和等于 target 的情况，所以还需要继续枚举，continue 外层循环。

3. 如果 a > 0 且 nums[a] == nums[a-1]，那么 nums[a] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue 外层循环。（可以放在循环开头判断。）

对于 nums[b] 的枚举（b 从 a+1 开始），也同样有类似优化：

1. 设 s = nums[a] + nums[b] + nums[b+1] + nums[b+2]。如果 s > target，由于数组已经排序，后面无论怎么选，选出的四个数的和不会比 s 还小，所以后面不会找到等于 target 的四数之和了。所以只要 s > target，就可以直接 break。

2. 设 s = nums[a] + nums[b] + nums[n−2] + nums[n−1]。如果 s < target，由于数组已经排序，nums[a] + nums[b] 加上后面任意两个数都不会超过 s，所以无法在后面找到另外两个数与 nums[a] 和 nums[b] 相加等于 target。但是后面还有更大的 nums[b]，可能出现四数之和等于 target 的情况，所以还需要继续枚举，continue。

3. 如果 b > a+1 且 nums[b] == nums[b-1]，那么 nums[b] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue。注意这里 b > a+1 的判断是必须的，如果不判断，对于示例 2 这样的数据，会直接 continue，漏掉符合要求的答案。

代码展示

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums.sort()ans = []n = len(nums)for a in range(n - 3): # 枚举第一个数x = nums[a]if a and x == nums[a - 1]: # 跳过重复数字continueif x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target: # 优化一breakif x + nums[-3] + nums[-2] + nums[-1] < target:  # 优化二continuefor b in range(a + 1, n - 2): # 枚举第二个数y = nums[b]if b > a + 1 and y == nums[b - 1]:  # 跳过重复数字continueif x + y + nums[b + 1] + nums[b + 2] > target:  # 优化一breakif x + y + nums[-2] + nums[-1] < target:  # 优化二continue# 使用双指针枚举第三个数和第四个数c = b + 1d =  n - 1while c < d:s = x + y + nums[c] + nums[d] # 四数之和if s > target:d -= 1elif s < target:c += 1else: # s == targetans.append([x, y, nums[c], nums[d]])c += 1while c < d and nums[c] == nums[c - 1]: # 跳过重复数字c += 1d -= 1while d > c and nums[d] == nums[d + 1]: # 跳过重复数字d -= 1return ans

复杂度分析

• 时间复杂度：$O(n^3)$，其中 n 为 nums 的长度。排序 O(n log n)。两重循环枚举第一个数和第二个数，然后 O(n) 双指针枚举第三个数和第四个数。所以总的时间复杂度为 $O(n^3)$。
• 空间复杂度：O(1)。忽略返回值和排序的栈开销，仅用到若干变量。

相关标签

• 数组
• 双指针
• 排序