跳转至

15. 三数之和（3Sum）

频次 ★★★★★ · 难度 🟡 · 高频：字节/美团/阿里

题目

数组中找出所有不重复的三元组 [a,b,c]，满足 a+b+c = 0。

示例： 

输入: [-1,0,1,2,-1,-4]
输出: [[-1,-1,2],[-1,0,1]]

思路

排序 + 固定一位 + 首尾双指针：

  1. 排序（去重和双指针单调性都靠它）
  2. 枚举第一个数 nums[i]，问题变成在 i+1..n-1 里找两数之和为 -nums[i]——即有序版两数之和
  3. 双指针 l/r：和小了 l++、大了 r--、命中后双侧跳过重复值

三层去重：i 跳重复、命中后 l 跳重复、r 跳重复。

代码

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break;                        // 最小数>0,后面不可能凑 0
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 第一位去重
        int l = i + 1, r = nums.length - 1, target = -nums[i];
        while (l < r) {
            int sum = nums[l] + nums[r];
            if (sum < target) l++;
            else if (sum > target) r--;
            else {
                res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                while (l < r && nums[l] == nums[l + 1]) l++;  // 命中后跳重复
                while (l < r && nums[r] == nums[r - 1]) r--;
                l++; r--;
            }
        }
    }
    return res;
}

复杂度

  • 时间：O(n²) —— 排序 O(n log n) + 外层 n × 内层双指针 O(n)
  • 空间：O(log n)（排序栈）；结果集不计

边界条件

  • 不足三个元素：返回空
  • 全 0 数组：只输出一组 [0,0,0]（去重逻辑保证）
  • 全正/全负：nums[i] > 0 剪枝或双指针自然无解

变式

    1. 最接近的三数之和：命中判断改为维护 |sum-target| 最小值，不需要去重
  • 18. 四数之和：再套一层循环，模式完全相同（k 数之和递归化）
  • 不允许排序（要求返回原下标）：退化为哈希两两组合，去重麻烦得多——说明排序是本题的核心预处理

易错点

三处去重分工不同，漏一处就出重复三元组：

去重点 位置 作用 漏掉的症状
❶ 外层 i 循环开头 i > 0 && nums[i] == nums[i-1] → continue 同一个固定值只枚举一次 [-1,0,1,2,-1,-4] 里两个 -1 各收一次 [-1,0,1]；[0,0,0,0] 收两次 [0,0,0]
❷ 内层 l 命中后 while (l < r && nums[l] == nums[l+1]) l++ 同一对组合只收一次 [-2,0,0,2,2] 里多个 0/2 组合重复命
❸ 内层 r 命中后 while (l < r && nums[r] == nums[r-1]) r-- 同上 同上
  • 去重时机：i > 0 && nums[i] == nums[i-1] 是和前一个 i 比，写成和后一个比会漏掉合法解
  • 去重顺序：❷❸ 必须在 l++ / r-- 之前，跳完重复值再各让一步；顺序反了会漏解
  • 跳重复时 l < r 必须作为循环条件（防指针越过彼此）；跳完后 l++ 和 r-- 两个都要执行，只动一侧会死循环或重复解
  • nums[i] > 0 才能 break（排序后最小数为正则无解）；nums[i] >= 0 是错的（会丢掉 [0,0,0]）

面试追问

  • 为什么不用哈希表做？ 能做（固定 i 后跑两数之和），但结果去重要对三元组做规范化比较，代码复杂且常数大；排序+双指针天然按序输出、去重只是跳指针
  • k 数之和怎么泛化？ 递归：k>2 时枚举第一个数递归 k-1，k=2 时双指针兜底，复杂度 O(n^(k-1))

关联题