三数之和 图解题解

这道题真正在问什么

在数组里找出所有满足 a + b + c = 0 的三元组，且结果不能包含重复的三元组——[-1,0,1] 和 [0,1,-1] 算同一个。两个要求叠加：既要找全，又要去重。去重恰恰是这题的真正难点，它直接决定了「先排序」不是可选项而是必选项。

为什么三层暴力行不通

三层循环枚举所有组合是 O(n³)，数组一大就跑不动；更麻烦的是去重——乱序数组里同一组数会以不同顺序被枚举到多次，要么把每个三元组排序后塞进集合判重（又慢又占空间），要么根本去不干净。这提示我们先给数组排序：排序后相同的数挤在一起，「跳过相邻重复值」就能完成全部去重；同时有序性还能反过来加速查找，一举两得。

排序后双指针为什么能省掉一层循环

固定第一个数 nums[i] 之后，剩下的问题是「在它右侧的有序区间里找两个数，和等于 0 - nums[i]」——这正是有序数组上的两数之和。左指针放区间头、右指针放区间尾：当前两数之和偏小时，只有左指针右移才可能让和变大；偏大时，只有右指针左移才可能让和变小。每一步都确定性地排除一个不可能参与解的端点，两个指针合计走一遍就穷尽了所有可能，把内层 O(n²) 的组合枚举压成 O(n)。这一步完全依赖有序性——乱序时「和小了往右走」不成立，这是必须先排序的第二个原因。

三处去重分别防住什么

去重有三处，缺一处就会输出重复三元组。外层一处：固定数与前一个固定数相同就跳过，防止两轮固定同一个值、产出完全相同的一批结果。内层两处：命中一个三元组后，左指针跳过与刚才相同的值、右指针同样跳过，防止同一个固定数下反复收到相同的搭档对。还有一个易忽略的动作——命中后左右指针要同时向内移动，只动一个的话另一头的值没变，下一轮要么重复命中要么白走一步。

复杂度怎么算，哪些边界会翻车

排序 O(n log n)，外层固定 n 次、内层双指针各是线性，总时间 O(n²)；排序原地进行、过程只用几个指针变量，不计输出结果的话空间 O(1)。边界上注意两处：数组不足 3 个数时直接返回空；全是同一个数的输入（比如 [0,0,0]）要靠三处去重才能正确地只输出一个 [0,0,0]，少一处就会重复。

Python

def threeSum(nums):
    nums.sort()                       # 先排序
    res = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i-1]:  # 固定数去重
            continue
        l, r = i + 1, n - 1           # 对撞双指针
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:   l += 1        # 和小了左扩
            elif s > 0: r -= 1        # 和大了右缩
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1; r -= 1
                while l < r and nums[l] == nums[l-1]: l += 1
                while l < r and nums[r] == nums[r+1]: r -= 1
    return res

C++

vector<vector<int>> threeSum(vector<int>& nums){
    sort(nums.begin(), nums.end());
    vector<vector<int>> res; int n = nums.size();
    for(int i = 0; i < n - 2; i++){
        if(i > 0 && nums[i] == nums[i-1]) continue;
        int l = i + 1, r = n - 1;
        while(l < r){
            int s = nums[i] + nums[l] + nums[r];
            if(s < 0) l++;
            else if(s > 0) r--;
            else{
                res.push_back({nums[i], nums[l], nums[r]});
                l++; r--;
                while(l < r && nums[l] == nums[l-1]) l++;
                while(l < r && nums[r] == nums[r+1]) r--;
            }
        }
    }
    return res;
}

Java

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);                       // 先排序
    List<List<Integer>> res = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 固定数去重
        int l = i + 1, r = n - 1;               // 对撞双指针
        while (l < r) {
            int s = nums[i] + nums[l] + nums[r];
            if (s < 0) l++;                     // 和小了左扩
            else if (s > 0) r--;               // 和大了右缩
            else {
                res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                l++; r--;
                while (l < r && nums[l] == nums[l - 1]) l++;
                while (l < r && nums[r] == nums[r + 1]) r--;
            }
        }
    }
    return res;
}