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 剪枝或双指针自然无解

变式

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

易错点

• 去重时机：i > 0 && nums[i] == nums[i-1] 是和前一个 i 比，写成和后一个比会漏掉合法解
• 命中后只移一侧指针 → 死循环或重复解；必须双跳再各进一步
• nums[i] > 0 才能 break（排序后最小数为正则无解）；nums[i] >= 0 是错的（0+0+0）

面试追问

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

关联题

• 同套路：1. 两数之和（哈希版）、167. 两数之和II-输入有序（本题内层就是它）
• 进阶：16. 最接近的三数之和、18. 四数之和
• 知识点：排序预处理换来双指针单调性——“先花 O(n log n) 买性质”是双指针/二分题的共同前提