三数之和

一、题目（LeetCode 15 · 中等 · Hot100）

给定整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i、j、k 互不相同且三数之和为 0。返回所有和为 0 且不重复的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]    // 不同的三元组值不能重复出现

二、思路演进

2.1 暴力：三重循环 + 去重

O(n³) 枚举，再用 Set 给结果去重。n = 3000 时约 2.7×10^10 次，超时；即便哈希去重，乱序元组的去重逻辑也极易写错。

2.2 第一改良：固定一个数，内层是"两数之和"

固定 a = nums[i]，剩下就是在 i+1..n-1 里找和为 -a 的两个数——两数之和 的原问题，哈希 O(n) 查表，总体 O(n²)。可行，但结果去重很痛：哈希无序，(a,b,c) 的排列组合都要归一化后判重，工程上易错。

2.3 最优：排序 + 固定一个 + 对撞双指针

先整体排序。排序带来的不止是双指针（有序数组两端对撞找目标和），更关键的是结构性去重：

• i 层：nums[i] == nums[i-1] 直接跳过——同一个数作为"最小值"只固定一次；
• 内层命中一组解后，left / right 各自跳过同值邻居再收缩——同一组值只记录一次。

不重不漏由"排序后相同值相邻"这一结构保证，不再需要任何 Set。为什么双指针正确：sum < 0 时左端太小，left 右移是唯一放大方向。sum > 0 时右端太大，right 左移是唯一缩小方向。与 盛最多水的容器 同源的排除法。

三、复杂度分析

• 排序 O(n log n)；主循环 i 走 n 次，内层 left+right 合计至多移动 n 次 → O(n²) 为主项。
• 空间 O(1)：不计返回值；排序的递归栈 O(log n) 通常忽略。

四、代码

package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_15 {

    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        // 期望 [[-1,-1,2],[-1,0,1]]
        System.out.println(threeSum(new int[]{0, 0, 0, 0}));
        // 期望 [[0,0,0]]：考察 b、c 层去重
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);                        // 一切去重与双指针的前提
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) {
                break;                            // 排序后最小值 > 0，三数之和不可能为 0
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;                         // i 层去重：同一个最小值只固定一次
            }

            int left  = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;                   // b 去重
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;                  // c 去重
                    }
                    left++;                       // 越过最后一组重复值，继续找下一组
                    right--;
                } else if (sum < 0) {
                    left++;                       // 和偏小，右移左端放大
                } else {
                    right--;                      // 和偏大，左移右端缩小
                }
            }
        }
        return ans;
    }

}

五、坑点

• i 层去重看 nums[i-1] 而不是 nums[i+1]：写成后者会把 [-1,-1,2] 漏掉——第二个 -1 被跳过后，这组解再也不会被固定出来。
• 命中一组解后不能 break 内层：同一 nums[i] 下可能还有别的 (b, c) 组合，去重后继续收缩双指针。
• 命中后 left、right 都要再动一格：去重 while 停在最后一个重复值上，必须再 left++; right-- 越过它，否则死循环。
• 剪枝 nums[i] > 0 依赖"和为 0"：四数之和里目标是任意值时该剪枝直接作废，且四数求和会溢出 int，要换 long。
• 去重 while 的条件记得带 left < right，否则越界。

六、变形追问

• 变体一（最接近的三数之和，LeetCode 16）：不求恰好相等求最接近 target。双指针每轮更新 abs(sum - target) 的最小值。移动规则不变，去重逻辑可以整个删除。
• 变体二（四数之和，LeetCode 18）：外面再套一层固定，内层仍是三数之和的模板，O(n³)。两层外循环各自去重，剪枝条件要用 long 比较。追问方向：能否证明 k 数之和的下界就是 O(n^(k-1))。理由：每层固定一个数，内层双指针已经把最后两层压成一层。

2026-10 新增（E 轨 · Hot100 第一批）。