LeetCode 15. 三数之和：从暴力枚举到双指针，彻底讲透去重、剪枝与边界控制

摘要

LeetCode 15. 三数之和（3Sum） 是一道非常经典的数组题。初学者通常会先想到三层循环暴力枚举，进一步会用 HashSet 去重，而标准高频解法则是：排序 + 枚举 + 双指针 + 过程去重 + 剪枝。

这篇文章将系统梳理三数之和的完整解题路线，覆盖：

  • 暴力枚举 + HashSet 去重
  • 双指针优化思路
  • i 的两种去重写法
  • left/right 去重的本质
  • 为什么要写 i < n - 2
  • 为什么要写 left < right && ...
  • 为什么 [0,0,0,0,0] 这个例子能很好地说明边界控制的重要性

读完这篇文章，不仅能写出这道题，还能真正理解这道题最核心的算法思想：排序、剪枝、双指针、过程去重、边界保护。

目录

文章目录

一、题目描述

给定一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]]，满足：

  • i != j
  • i != k
  • j != k
  • nums[i] + nums[j] + nums[k] == 0

要求返回 所有不重复的三元组。

示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

二、这道题真正难在哪里

很多人第一次做这道题时，会把重点放在“怎么找三个数加起来等于 0”。但实际上，这道题真正的难点主要有三点：

1. 如何把时间复杂度从 O(n^3) 优化到 O(n^2)

最容易想到的是三层循环暴力枚举，但这只是入门思路。标准写法需要优化到 O(n^2)。

2. 如何正确去重

三数之和里的重复，不是简单的一层重复，而是多层重复：

第一类：第一个数重复

例如排序后：

[-4, -1, -1, 0, 1, 2]

如果第一个 -1 已经作为起点处理过，那么第二个 -1 再作为起点，很多结果都会重复。

第二类：左右指针重复

即使起点固定，left 和 right 也可能落在连续重复值中。如果不跳过，同一个三元组会重复加入结果。

第三类：顺序不同但内容相同

例如：

[-1, 0, 1]
[0, -1, 1]
[1, -1, 0]

它们本质上是同一个解，只是排列顺序不同。

3. 如何保证边界安全

这道题是典型的“思路不难，细节很容易写错”的题目。常见错误包括：

  • right 去重方向写反
  • 去重时没有写 left < right
  • 外层循环边界写得不够严谨
  • 去重位置放错导致漏解或重解

三、为什么排序是整道题的起点

无论是暴力解法还是双指针解法，排序几乎都是第一步。

排序的作用有三点：

1. 固定三元组内部顺序

排序后，三元组天然满足：

a <= b <= c

这样就不会出现 [0,-1,1] 和 [-1,0,1] 被误判为不同答案的问题。

2. 让重复值相邻

排序之后，相同元素会聚在一起，去重时只需要比较相邻元素即可。

3. 让双指针移动有依据

双指针之所以能成立，是因为数组有序：

  • 当前和太小，左指针右移
  • 当前和太大，右指针左移

如果数组无序，指针移动就没有方向意义。

四、解法一：暴力枚举 + HashSet 去重

1. 思路

最直接的做法就是三层循环：

  • 枚举所有 i < j < k
  • 若 nums[i] + nums[j] + nums[k] == 0，则加入结果
  • 为防止重复答案，使用 HashSet<List<Integer>> 去重

这种方法的本质是：

先生成所有候选答案，再在结果层面统一去重。

这叫 结果去重。

2. 代码实现（带详细注释）

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 先排序：
        // 1. 固定三元组内部顺序，便于 Set 去重
        // 2. 为后续优化解法（双指针）打基础
        int[] resArr = SortNums(nums);

        // Set 用于自动去重
        // 这里存储的是 List<Integer>
        // Java 中 List 的 equals() 和 hashCode() 是按内容比较的
        Set<List<Integer>> resSet = new HashSet<>();

        // 三重循环暴力枚举所有 i < j < k 的组合
        for (int i = 0; i < resArr.length; i++) {
            for (int j = i + 1; j < resArr.length; j++) {
                for (int k = j + 1; k < resArr.length; k++) {

                    // 找到和为 0 的三元组
                    if (resArr[i] + resArr[j] + resArr[k] == 0) {
                        // 由于数组已经排序，所以三元组内部顺序固定
                        // 相同内容的三元组会被 HashSet 自动去掉
                        resSet.add(Arrays.asList(resArr[i], resArr[j], resArr[k]));
                    }
                }
            }
        }

        return new ArrayList<>(resSet);
    }

    public static int[] SortNums(int[] nums) {
        // 冒泡排序
        // 实际刷题中更推荐 Arrays.sort(nums)
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[j] < nums[j - 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }
            }
        }
        return nums;
    }
}

3. 为什么 HashSet<List<Integer>> 可以去重

因为 Java 中 List 的 equals() 和 hashCode() 是按元素内容比较的，而不是按地址比较。

例如：

Set<List<Integer>> set = new HashSet<>();
set.add(Arrays.asList(-1, 0, 1));
set.add(Arrays.asList(-1, 0, 1));
System.out.println(set.size()); // 1

这也是为什么这里可以用 HashSet<List<Integer>> 去重。

4. 复杂度分析

  • 排序：O(n^2)（若用冒泡排序）
  • 三层循环：O(n^3)
  • 总时间复杂度：O(n^3)
  • 空间复杂度：O(k)，k 为答案数量

5. 这种写法的优缺点

优点
  • 逻辑直观
  • 易于理解
  • 适合建立题感
缺点
  • 时间复杂度太高
  • 去重是“事后去重”
  • 数据稍大就容易超时

五、什么叫剪枝

在进入双指针之前，先明确一个重要术语：剪枝（Pruning）。

1. 剪枝的定义

剪枝就是：

在搜索尚未完全展开时，提前判断某一部分不可能产生答案，于是直接停止或跳过。

它的核心思想是：

  • 不是把所有情况都试完再排除
  • 而是提前发现“这一段一定无解”，因此直接不搜

这就叫“剪掉无效分支”。

2. 本题中的经典剪枝

在排序后的数组中，如果当前枚举的第一个数已经大于 0：

if (nums[i] > 0) break;

就可以直接终止外层循环。

为什么成立？

因为数组已排序，若当前 nums[i] > 0，则后面的 nums[left]、nums[right] 一定满足：

nums[left] >= nums[i] > 0
nums[right] >= nums[i] > 0

那么三者之和一定大于 0，不可能再等于 0。

为什么是 break 而不是 continue

因为从当前 i 往后，所有数都会更大，所以不仅这一轮无解，后面所有轮也都无解。
因此应该直接结束整个循环，而不是只跳过当前一轮。

六、解法二：排序 + 枚举 + 双指针 + i 后置去重

1. 核心思路

固定第一个数 nums[i] 后，问题转化为：

在区间 [i+1, n-1] 中寻找两个数 nums[left] 和 nums[right]，使得：

nums[left] + nums[right] == -nums[i]

由于数组有序，所以：

  • 和太小：left++
  • 和太大：right--
  • 和正好：记录答案，然后继续去重

2. 代码实现（带详细注释）

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 排序，使数组有序
        int[] resArr = SortNums(nums);
        int n = resArr.length;
        List<List<Integer>> resList = new ArrayList<>();

        if (n < 3) return resList;

        // 这里没有把 i++ 写进 for 的更新表达式
        // 因为一轮结束后还要手动跳过重复的 i
        for (int i = 0; i < n; ) {

            // 剪枝：
            // 当前值已经大于 0，则后续不可能再组成和为 0 的三元组
            if (resArr[i] > 0) break;

            int left = i + 1;
            int right = n - 1;
            int target = -resArr[i];

            while (left < right) {
                int sum = resArr[left] + resArr[right];

                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    // 找到一个合法三元组
                    resList.add(new ArrayList<>(
                            Arrays.asList(resArr[i], resArr[left], resArr[right])
                    ));

                    // 当前 left 和 right 已经参与过答案构造
                    // 先收缩一步，再进行去重
                    left++;
                    right--;

                    // left 去重：
                    // left 已经右移，所以与 left - 1 比较
                    while (left < right && resArr[left] == resArr[left - 1]) {
                        left++;
                    }

                    // right 去重：
                    // right 已经左移，所以与 right + 1 比较
                    while (left < right && resArr[right] == resArr[right + 1]) {
                        right--;
                    }
                }
            }

            // 一轮结束后，手动推进 i
            i++;

            // 跳过重复的 i
            while (i < n && resArr[i] == resArr[i - 1]) {
                i++;
            }
        }

        return resList;
    }

    public static int[] SortNums(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[j] < nums[j - 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }
            }
        }
        return nums;
    }
}

3. 这种 i 去重方式的特点

这一版中，i 的去重写在循环尾部：

i++;
while (i < n && resArr[i] == resArr[i - 1]) {
    i++;
}

含义是：

  • 当前 i 对应的所有答案都找完之后
  • 再手动推进到下一个不同值

这是一种 后置去重 写法。

七、解法三：排序 + 枚举 + 双指针 + i 前置去重

这也是更常见、更适合面试的写法。

1. 核心思路

双指针主体逻辑不变，只是把 i 的去重提前到循环一开始：

if (i > 0 && nums[i] == nums[i - 1]) continue;

这样写的好处是：

  • for 循环本身负责更新 i
  • 控制流更紧凑
  • 代码更符合主流面试写法

2. 代码实现（带详细注释）

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int[] resArr = SortNums(nums);
        int n = resArr.length;
        List<List<Integer>> resList = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            // 剪枝：
            // 数组有序，一旦当前数大于 0，
            // 后面所有数都不会比它小，不可能再组成和为 0 的三元组
            if (resArr[i] > 0) break;

            // i 去重（前置去重）：
            // 当前值与前一个值相同，说明这一轮会产生重复答案
            if (i > 0 && resArr[i] == resArr[i - 1]) continue;

            int left = i + 1;
            int right = n - 1;
            int target = -resArr[i];

            while (left < right) {
                int sum = resArr[left] + resArr[right];

                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    resList.add(new ArrayList<>(
                            Arrays.asList(resArr[i], resArr[left], resArr[right])
                    ));

                    left++;
                    right--;

                    while (left < right && resArr[left] == resArr[left - 1]) {
                        left++;
                    }

                    while (left < right && resArr[right] == resArr[right + 1]) {
                        right--;
                    }
                }
            }
        }

        return resList;
    }

    public static int[] SortNums(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[j] < nums[j - 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }
            }
        }
        return nums;
    }
}

八、为什么推荐面试中写成 i < n - 2

在很多代码中，外层循环写成：

for (int i = 0; i < n; i++)

从运行角度看，有时也能通过，因为当 i 接近数组末尾时，left < right 很快不成立。

但从代码严谨性来看，更推荐写成：

for (int i = 0; i < n - 2; i++)

为什么？

因为三数之和需要三个元素：

  • 一个固定的 i
  • 一个 left
  • 一个 right

如果 i >= n - 2，那么 i 后面最多只剩下 1 个元素，已经不可能再组成三元组。

也就是说：

  • 当 i = n - 2 时，后面只剩 1 个数
  • 当 i = n - 1 时，后面一个数都没有

这两种情况根本没有继续枚举的意义。

这样写的优点

1. 语义更准确

明确表达了“后面至少还要有两个位置”。

2. 少做无意义循环

避免在数组尾部做无效枚举。

3. 更符合面试官预期

体现出写代码时对边界条件的主动控制。

九、标准面试写法（推荐背熟版）

下面给出一版更推荐的正式写法，包括：

  • Arrays.sort(nums) 排序
  • i < n - 2
  • i 前置去重
  • left/right 去重
  • 剪枝逻辑
import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        // 使用库排序，效率更高
        Arrays.sort(nums);

        int n = nums.length;

        // 为什么是 i < n - 2？
        // 因为固定 nums[i] 后，后面至少还要留两个位置给 left 和 right
        for (int i = 0; i < n - 2; i++) {

            // 剪枝：
            // 排序后，如果当前 nums[i] > 0，
            // 那么后面的 nums[left]、nums[right] 也一定 >= nums[i] > 0
            // 三者之和必然 > 0，因此可以直接结束整个循环
            if (nums[i] > 0) break;

            // i 去重：
            // 若当前值与前一个值相同，则这一轮得到的结果会与上一轮重复
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = n - 1;

            // 在区间 [left, right] 内寻找两个数，使三数之和为 0
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum < 0) {
                    // 当前和偏小，需要更大的数
                    left++;
                } else if (sum > 0) {
                    // 当前和偏大，需要更小的数
                    right--;
                } else {
                    // 找到一个合法三元组
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 当前这组 left / right 已经使用过
                    // 先收缩一步，再跳过重复值
                    left++;
                    right--;

                    // left 去重：
                    // left 已经右移，所以与 left - 1 比较
                    // 如果相同，说明仍然落在重复值区间
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }

                    // right 去重：
                    // right 已经左移，所以与 right + 1 比较
                    // 如果相同，说明仍然落在重复值区间
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }

        return res;
    }
}

十、为什么 left/right 去重一定要写成 left < right && ...

这部分是整道题最精细、也最容易被忽视的细节。

去重代码如下：

while (left < right && nums[left] == nums[left - 1]) {
    left++;
}

while (left < right && nums[right] == nums[right + 1]) {
    right--;
}

这段代码中，left < right 这一层判断不是装饰，而是非常关键。

它同时承担两个职责：

1. 保证指针仍在合法搜索区间内

双指针搜索的有效区间始终是：

[left, right]

只有当：

left < right

时，区间内才至少还有两个位置，才有继续寻找答案的意义。

一旦：

left >= right

就说明搜索已经结束，再去重没有意义。

2. 防止越界和无效访问

去重时如果没有先判断 left < right，当指针已经相遇甚至交错后，代码仍可能继续访问数组元素，造成无效比较，甚至在某些写法中导致越界风险。

所以：

left < right && ...

本质上是“边界闸门”。

十一、用 [0,0,0,0,0] 说明这段代码为什么写得非常好

这个例子特别适合说明：

  • 为什么要去重
  • 为什么要加 left < right
  • 为什么这段代码既安全又优雅

1. 排序后数组不变

[0,0,0,0,0]

2. 第一次枚举：i = 0

当前：

nums[i] = 0
left = 1
right = 4
sum = 0 + 0 + 0 = 0

找到一个合法三元组：

[0,0,0]

3. 找到答案后先收缩指针

执行：

left++;
right--;

此时变为：

left = 2
right = 3

4. 进入 left 去重

while (left < right && nums[left] == nums[left - 1]) {
    left++;
}

此时：

  • left = 2
  • right = 3
  • nums[2] == nums[1] == 0

成立，因此 left++。

变为：

left = 3

再次判断：

left < right

现在已经不成立，因为：

left = 3
right = 3

所以 left 去重立即停止。

5. 再进入 right 去重

while (left < right && nums[right] == nums[right + 1]) {
    right--;
}

这时一开始就会先判断：

left < right

但现在：

left = 3
right = 3

不成立，所以根本不会继续访问 nums[right] 和 nums[right + 1]。

6. 这说明了什么

这段代码的优秀之处体现在三点：

第一，能去重

它只会保留一个 [0,0,0]，不会因为多个 0 而重复加入结果。

第二，能防止无效访问

当指针已经相遇时，去重操作立即停止。

第三，能防止边界问题

不会在搜索已经结束的区间上继续访问元素。

如果去掉 left < right，那么在这种大量重复值的数组中，代码很容易写出错误行为。

十二、left/right 去重到底去掉了什么

举一个更典型的例子：

[-2, 0, 0, 0, 2, 2]

假设当前固定 -2，第一次找到：

[-2, 0, 2]

如果不对 left 和 right 去重：

  • 下一个 0 还会再次和 2 组成相同答案
  • 下一个 2 还会再次和 0 组成相同答案

所以，去重的本质是：

同值元素在当前这一层搜索中，只保留第一个代表位置，其余全部跳过。

这就是双指针解法中的 过程去重。

十三、三种解法的本质对比

1. 暴力 + Set：结果去重

思路是：

  • 先把所有可能答案找出来
  • 再用 HashSet 去掉重复

这是“事后去重”。

2. 双指针：过程去重

思路是：

  • 在搜索过程中主动跳过重复值
  • 让重复答案根本不会产生

这是“过程去重”。

3. 两种双指针写法的区别

后置去重版
for (int i = 0; i < n; ) {
    ...
    i++;
    while (i < n && nums[i] == nums[i - 1]) i++;
}

特点：

  • 当前轮结束后再推进到下一个合法起点
  • 需要手动维护 i
前置去重版
for (int i = 0; i < n - 2; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    ...
}

特点：

  • 当前轮一开始就判断是否重复
  • for 循环自然负责推进 i
  • 更紧凑、更适合面试

十四、复杂度分析

1. 暴力解法

  • 排序：O(n^2)（冒泡）
  • 三层循环：O(n^3)
  • 总时间复杂度：O(n^3)
  • 空间复杂度：O(k)

2. 双指针解法

若使用 Arrays.sort(nums)：

  • 排序：O(n log n)
  • 外层枚举：O(n)
  • 内层双指针整体扫描：O(n)
  • 总时间复杂度：O(n^2)

空间复杂度通常为 O(1)（不计答案存储）。

十五、面试高频追问总结

1. 为什么 HashSet<int[]> 不行

因为数组默认按地址比较，不按内容比较：

int[] a = {1,2,3};
int[] b = {1,2,3};
System.out.println(a.equals(b)); // false

所以 HashSet<int[]> 不能完成内容去重。

2. 为什么 nums[i] > 0 就能直接 break

因为数组有序，后面的数只会更大，三数之和一定大于 0，不可能再有解。

3. 为什么推荐写成 i < n - 2

因为固定 i 后，后面至少还要剩两个位置给 left 和 right，否则不可能组成三元组。

4. 为什么找到答案后要先 left++、right--

因为当前这组 left/right 已经参与过答案构造，不应该被再次使用。

5. 为什么去重时一定要加 left < right

因为它既是合法搜索区间约束，也是边界保护条件。没有它，代码容易在重复值密集区写出无效访问甚至越界风险。

十六、整道题的学习路线总结

真正掌握三数之和，建议按以下顺序理解：

第一阶段：先会暴力

先理解题目在求什么，为什么会出现重复答案。

第二阶段：理解排序

排序不仅是为了去重，更是为了支撑双指针和剪枝。

第三阶段：掌握双指针降维

固定一个数，把三数之和转化成两数之和。

第四阶段：彻底理解去重

  • i 去重：防止重复起点
  • left 去重：防止重复第二个数
  • right 去重：防止重复第三个数

第五阶段：掌握剪枝与边界保护

  • nums[i] > 0：直接结束
  • i < n - 2：保证后面至少还有两个数
  • left < right && ...：保证去重只发生在合法搜索区间

十七、结语

三数之和是一道非常典型的“从朴素解走向标准解”的算法题。它训练的不是简单的代码背诵，而是一种更重要的解题思维：

当一个问题既涉及组合搜索，又涉及重复答案时，
应优先考虑：
能否通过排序把无序问题转化为有序问题；
能否通过双指针替代暴力枚举；
能否通过剪枝提前终止无效搜索；
能否在搜索过程中主动跳过重复路径，而不是事后统一清理。

把这道题学透之后，再去看四数之和、最接近的三数之和、两数之和 II 等题，会轻松很多。因为其中最核心的方法论已经建立起来了：

排序、枚举、双指针、剪枝、过程去重、边界保护。

# leetcode # 剪枝 # 算法
Logo
AI编程社区

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

码道 · 寻艺——从零构建“非遗交互式对话平台“的完整实践

avatar AI编程社区

码道：用 Python + FastAPI 快速构建一个学生信息管理接口：从零到 Swagger 在线文档

在日常开发和教学中，我们经常需要一套简单、可控、能快速上手的后端接口来演示"前后端分离"、练习 Restful API 设计，或者作为前端联调的 Mock 服务。传统做法往往是搭一套完整的 Web 工程：配置数据库、编写 DAO、引入 ORM、做请求分发……一套流程下来，光环境搭建就要花去不少时间，对于想快速验证想法、或者刚入门 API 开发的同学来说，显得过于沉重。

avatar AI编程社区

码道：从零构建学生信息管理系统 API：FastAPI 内存版 CRUD 项目全解析

FastAPI 的强大，很大程度上来自 Pydantic 的校验能力。我们写下类型声明，FastAPI 在运行时自动把它变成边界检查器。name：字符串，长度限制 1 到 50；age：整数，限制在 6 到 120 之间（ge大于等于、le小于等于）；gender：字符串，用正则限定只能是"男"“女”“其他”；email：邮箱格式字符串；grade与major：可选字段，代表班级和专业方向。

avatar AI编程社区