18. 4Sum

题目

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

1
2
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

1
2
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

题目大意

在整数数组中找出所有不重复的四元组，使得四个数的和等于目标值 target。要求四元组不能重复，但顺序可以不同。

你选用何种方法解题？

本题的核心是高效查找四元组并去重。可以看作是三数之和问题的扩展。

方法 时间复杂度 空间复杂度 是否推荐
排序 + 双层循环 + 双指针 O(n³) O(log n) ~ O(n) 推荐
哈希表 O(n³) O(n) 不推荐
暴力枚举 O(n⁴) O(1) 不推荐

方法选择理由：

  • 排序 + 双层循环 + 双指针：通过排序实现 O(n log n) 的预处理，然后用两层循环固定前两个数，双指针查找后两个数，整体 O(n³)。排序还能自然处理去重问题。
  • 哈希表：虽然也是 O(n³)，但需要额外 O(n) 空间存储哈希表，且去重逻辑复杂。
  • 暴力枚举：O(n⁴) 时间复杂度，无法通过较大规模测试用例。

解题过程

问题分析

输入：整数数组 nums，目标值 target
输出：所有不重复的四元组 [a, b, c, d]，满足 a + b + c + d = target

关键约束：四元组不能重复。

核心洞察

  1. 排序的价值：排序后可以利用有序性进行双指针查找，同时便于跳过重复元素。
  2. 转化为两数之和：固定前两个数 nums[a] 和 nums[b]，问题转化为在剩余元素中找两数之和为 target - nums[a] - nums[b]。
  3. 剪枝优化：
    • 最小和剪枝：如果当前最小可能和已大于 target，后续只会更大
    • 最大和剪枝：如果当前最大可能和仍小于 target，直接跳过当前元素
  4. 去重策略：排序后，相同元素会相邻，只需跳过与前一个相同的元素即可。

算法流程

以 nums = [1, 0, -1, 0, -2, 2], target = 0 为例：

步骤 1：排序 → [-2, -1, 0, 0, 1, 2]

步骤 2：外层循环枚举第一个数 nums[a]：

a nums[a] min_sum max_sum 操作
0 -2 -2 + (-1) + 0 + 0 = -3 -2 + 0 + 1 + 2 = 1 继续
1 -1 -1 + 0 + 0 + 1 = 0 -1 + 0 + 1 + 2 = 2 继续
... ... ... ... ...

步骤 3：内层循环枚举第二个数 nums[b]，然后用双指针查找：

a b x y target-xy c d s 操作
0 1 -2 -1 3 2 5 -2-1+0+2=-1 s < target, c++
0 1 -2 -1 3 3 5 -2-1+0+2=-1 s < target, c++
0 1 -2 -1 3 4 5 -2-1+1+2=0 记录 [-2,-1,1,2]
... ... ... ... ... ... ... ... ...

这些方法具体怎么运用？

方法：排序 + 双层循环 + 双指针（推荐）

数据结构：排序后的数组 + 两个指针（c, d）

核心逻辑：

  1. 排序：先对数组排序，时间 O(n log n)
  2. 外层循环：遍历每个元素作为四元组的第一个数 nums[a]
    • 跳过重复的 nums[a]（与前一个相同则跳过）
    • 最小和剪枝：计算 nums[a] + nums[a+1] + nums[a+2] + nums[a+3]，若大于 target 则 break
    • 最大和剪枝：计算 nums[a] + nums[-3] + nums[-2] + nums[-1]，若小于 target 则 continue
  3. 内层循环：遍历每个元素作为四元组的第二个数 nums[b]
    • 跳过重复的 nums[b]（与前一个相同则跳过）
    • 最小和剪枝：计算 nums[a] + nums[b] + nums[b+1] + nums[b+2]，若大于 target 则 break
    • 最大和剪枝：计算 nums[a] + nums[b] + nums[-2] + nums[-1]，若小于 target 则 continue
  4. 双指针：在 [b+1, n-1] 范围内查找两数之和为 target - nums[a] - nums[b]
    • c = b + 1，d = n - 1
    • 若 nums[c] + nums[d] < target - x - y → c++
    • 若 nums[c] + nums[d] > target - x - y → d--
    • 若等于 → 记录结果，同时跳过两端的重复元素

边界情况处理：

边界情况 处理方式
数组长度 < 4 直接返回空列表
第一个元素的最小和 > target 直接退出循环
第一个元素的最大和 < target 跳过当前元素
重复的第一个元素 if a > 0 and nums[a] == nums[a-1] 跳过
重复的第二个元素 if b > a + 1 and nums[b] == nums[b-1] 跳过
找到解后两端有重复元素 移动 c/d 直到指向不同的值

复杂度

方法 时间复杂度 空间复杂度 说明
排序 + 双层循环 + 双指针 O(n³) O(log n) ~ O(n) 排序 O(n log n) + 双层循环 O(n²) + 双指针 O(n)；空间取决于排序算法的实现
哈希表 O(n³) O(n) 需要额外哈希表存储已访问元素
暴力枚举 O(n⁴) O(1) 四重循环，无法通过大数据测试

常数因子分析：排序 + 双层循环 + 双指针的实际运行速度通常优于哈希表，因为：

  • 排序后的数组具有更好的缓存局部性
  • 无需额外的哈希表操作开销
  • 剪枝优化可以提前终止无效搜索

总结与最佳选择

最快算法：排序 + 双层循环 + 双指针。实际测试中，剪枝优化能显著减少迭代次数。

工程最优选择：排序 + 双层循环 + 双指针。理由如下：

  1. 时间效率高：O(n³) 时间复杂度，配合剪枝优化效果更好
  2. 空间效率好：仅需排序所需的 O(log n) ~ O(n) 空间
  3. 代码简洁：去重逻辑自然融入排序后的遍历
  4. 稳定性强：不会受哈希冲突影响，性能稳定

各方法适用场景：

  • 排序 + 双层循环 + 双指针：首选方案，适用于绝大多数情况
  • 哈希表：仅在无法修改原数组顺序时考虑（本题不适用）
  • 暴力枚举：仅用于教学对比

Code

方法：排序 + 双层循环 + 双指针（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        """
        排序 + 双层循环 + 双指针法：
        1. 先排序，便于双指针查找和去重
        2. 两层循环固定前两个数
        3. 用双指针在剩余区间查找满足条件的后两个数
        """
        nums.sort()
        ans = []
        n = len(nums)
        
        # 枚举第一个数
        for a in range(n - 3):
            x = nums[a]
            # 跳过重复数字
            if a > 0 and x == nums[a - 1]:
                continue
            
            # 优化一：最小和已经大于target，后面只会更大
            if x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target:
                break
            # 优化二：最大和小于target，跳过当前第一个数
            if x + nums[-3] + nums[-2] + nums[-1] < target:
                continue
            
            # 枚举第二个数
            for b in range(a + 1, n - 2):
                y = nums[b]
                # 跳过重复数字
                if b > a + 1 and y == nums[b - 1]:
                    continue
                
                # 优化一：最小和已经大于target，后面只会更大
                if x + y + nums[b + 1] + nums[b + 2] > target:
                    break
                # 优化二：最大和小于target，跳过当前第二个数
                if x + y + nums[-2] + nums[-1] < target:
                    continue
                
                # 双指针枚举第三和第四个数
                c = b + 1
                d = n - 1
                
                while c < d:
                    s = x + y + nums[c] + nums[d]
                    
                    if s > target:
                        d -= 1
                    elif s < target:
                        c += 1
                    else:
                        # 找到解，记录四元组
                        ans.append([x, y, nums[c], nums[d]])
                        # 跳过重复元素
                        c += 1
                        while c < d and nums[c] == nums[c - 1]:
                            c += 1
                        d -= 1
                        while d > c and nums[d] == nums[d + 1]:
                            d -= 1
        
        return ans

方法二：哈希表（不推荐，仅供对比）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        """
        哈希表法：固定前两个数，用哈希表存储已访问元素
        注意：去重逻辑复杂，代码可读性差
        """
        n = len(nums)
        result = set()
        
        nums.sort()
        
        for a in range(n):
            for b in range(a + 1, n):
                seen = set()
                for c in range(b + 1, n):
                    need = target - nums[a] - nums[b] - nums[c]
                    if need in seen:
                        result.add((nums[a], nums[b], need, nums[c]))
                    seen.add(nums[c])
        
        return [list(quadruplet) for quadruplet in result]