4Sum
给定一个整数列表 nums 和一个整数 target。返回所有四元组 [a, b, c, d]，其中四个值分别位于 nums 的四个不同位置，且它们的和为 target。每个四元组中的值都按非递减顺序排列。如果相同的四个值可以从不同位置选出，该四元组也只需出现一次。答案按第一个值、第二个值、第三个值依次排序。如果没有符合条件的四元组，则返回一个空列表。
函数
- numsinteger-array
- 可供选择的数字，至少一个
- targetinteger
- 每个四元组的和必须达到
- 返回值integer-2d-array
- 和为 target 的不同四元组，每个四元组都已排序，列表也已排序；如果没有，则为空列表
约束条件
1 ≤ nums.length ≤ 200-108 ≤ nums[i] ≤ 108-109 ≤ target ≤ 109- 任意四个值的和介于
-4 × 108和4 × 108之间，因此可以用 32 位整数表示。 - 四个值都相同的四元组只算作一个。
示例
- 输入
- nums = [3, -1, 0, 2, -2, 1, -3]target = 1
- 输出
- [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
- 解释
- 四组四元组的和都是 1，例如
-3 + (-1) + 2 + 3。以 -3 开头的两组排在前面，并按第二个值排序：-1 在 0 前面。
- 输入
- nums = [4, 4, 4, 4, 4, 4]target = 16
- 输出
- [[4, 4, 4, 4]]
- 解释
- 从 6 个位置中选择 4 个位置，共有 15 种选择，每种选择都会得到 4 个 4，相加为 16，因此
[4, 4, 4, 4]会出现一次。
- 输入
- nums = [1, 5, 2, 9]target = 3
- 输出
- []
- 解释
- 唯一的选择是全部 4 个数字，而
1 + 5 + 2 + 9 = 17，不是 3，所以答案是一个空列表。
进阶
统计值之和为 target 的四个位置组合数量，而不是不同的四元组数量。第二个示例的结果是 15。你能用 O(n²) 完成吗？
提示
逐个打开提示，每个都会多透露一点。
先对列表进行排序。相等的值会相邻排列，因此从左到右任意选取 4 个值，它们都按非递减顺序排列。
固定前两个值
nums[i]和nums[j]，且i < j。剩下的部分是在j右侧的已排序值中找到一对，使它们的和等于target - nums[i] - nums[j]。这就是在已排序列表中解决两数之和问题。用两个指针解答这道题：
lo位于j后面，hi位于最后一个索引处。总和低于目标值时，将lo向右移动；高于目标值时，将hi向左移动。跳过值与对应循环上次尝试的值相同的i或j，匹配成功后，继续移动lo，直到它的值发生变化。
题解
检查每四个位置的组合需要 O(n⁴)，重复的值会让同一个四元组被多次生成。将 3Sum 的简化方法再推进一层：先排序，用两层循环固定前两个值，再用双指针查找最后一对值，并在每一层跳过重复值。
尝试每一组四个
结果正确，但无法在最大的测试中运行完毕
思路
先排序，这样位置 i < j < k < l 上的值就会按非递减顺序排列，每个四元组也都会按正确顺序输出。四层嵌套循环会遍历所有四个位置的选择。为了避免重复，如果循环要检查的下一个位置上的值与前一步检查的值相同，就跳过该位置。对于 6 个 4，每层循环都只检查第一个位置，因此 [4, 4, 4, 4] 只会输出一次，而不是 15 次。
对于 200 个数字，共有 64,684,950 组由 4 个数字组成的组合；n 翻倍时，组合数大约会增长到 16 倍。
算法
- 对
nums排序。 - 嵌套四个循环，遍历
i < j < k < l，每个循环都从外层循环当前位置的后一位开始。 - 在每个循环中，跳过不是循环起始位置且与前一个位置的值相同的位置。
- 当四个值的和等于
target时，记录[nums[i], nums[j], nums[k], nums[l]]。循环会按排序后的顺序生成这些结果。
def fourSum(nums, target):
nums = sorted(nums)
n = len(nums)
quads = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue # same first value as the round before
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # same second value as the round before
for k in range(j + 1, n - 1):
if k > j + 1 and nums[k] == nums[k - 1]:
continue # same third value as the round before
for l in range(k + 1, n):
if l > k + 1 and nums[l] == nums[l - 1]:
continue # same fourth value as the round before
if nums[i] + nums[j] + nums[k] + nums[l] == target:
quads.append([nums[i], nums[j], nums[k], nums[l]])
return quads排序、两个循环、双指针
思路
固定 nums[i] 和 nums[j] 后，剩下的问题就是找一对数：在 j 右边找到两个值，使它们的和等于 target - nums[i] - nums[j]。对于已排序的列表，只需扫描一遍就能找到答案。将 lo 设为 j+1，将 hi 设为最后一个索引。和小于 target 时，lo 向右移动；和大于 target 时，hi 向左移动。
每次移动都会排除一个不可能出现在答案中的值。如果和太小，即使取剩余值中最大的 nums[hi]，与 nums[lo] 相加也不够，所以可以排除 nums[lo]。和太大时，出于相反的原因，可以排除 nums[hi]。一对 (i, j) 最多需要 n 次移动，因此 n²/2 对的总开销为 O(n³)。
在第一个示例中，当 i 指向 -3、j 指向 -1 时，lo 从 0 移动，越过 1 到达 2，此时 -3 + (-1) + 2 + 3 = 1。
算法
- 对
nums排序。 - 对于每个
i，如果i > 0且nums[i]等于nums[i-1]，则跳过它。 - 对于
i之后的每个j，如果j > i+1且nums[j]等于nums[j-1]，则跳过它。 - 设置
lo = j+1和hi = n-1。当lo < hi时，将四个值的和与target比较：如果和更小，就将lo向右移动；如果和更大，就将hi向左移动。 - 如果匹配，就记录这个四元组，移动两个指针，然后在
lo仍指向它刚才使用的值时继续递增lo。
def fourSum(nums, target):
nums = sorted(nums)
n = len(nums)
quads = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue # this first value was already handled
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # this second value was already handled
lo, hi = j + 1, n - 1
while lo < hi:
total = nums[i] + nums[j] + nums[lo] + nums[hi]
if total < target:
lo += 1
elif total > target:
hi -= 1
else:
quads.append([nums[i], nums[j], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
return quads
易错点和边界情况
- 每当
nums[j]等于nums[j-1]时跳过j。当j = i+1时，它会与使用值i进行比较，因此对于目标值为 8 的[2, 2, 2, 2, 2]，会遗漏[2, 2, 2, 2]。 - 照搬 3Sum 的提前退出条件
nums[i] > target。对于[-5, -4, -3, -2, -1]和目标值 -10，循环会在 -5 处停止，并遗漏[-4, -3, -2, -1]。 - 长度小于 4 的列表。只有一个或两个数字时，
n-3为负数：在 Swift 中，0..<(n - 3)会触发陷阱，而 Rust 的usize上的n - 3会发生下溢。应先返回空列表。 - 将四元组收集到哈希集合中，然后不排序就返回。
常见问题3
4Sum 的时间复杂度是多少？
O(n³)。两个循环会选出大约 n²/2 对 (i, j)，每一对都会进行一次最多 n 步的双指针扫描；与之相比，O(n log n) 排序的开销很小。
如何将 4Sum 推广到 kSum？
在已排序的列表上编写 kSum(nums, target, k)。当 k = 2 时，它会执行双指针扫描。对于更大的 k，它会遍历第一个值，跳过重复值，并在右侧的值中使用 k-1 和 target - nums[i] 调用自身。每一层都会增加一个 n 因子，因此 kSum 的时间复杂度为 O(n^(k-1))。
4Sum 可以在 O(n²) 时间内解决吗？
你可以将 n²/2 个数对之和分组存入哈希映射，并让每个数对与和为 target 减去自身之和的数对匹配。当只有少量数对的和相同时，这种方法很快；但某个和可能对应 O(n²) 个数对，因此最坏情况下并不比 O(n³) 好。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def fourSum(nums, target):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, -1, 0, 2, -2, 1, -3] target = 1
预期输出
[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]