三数之和与双指针：力扣Hot 100经典题解，Java实现与去重细节

刷力扣 Hot 100 的日子，很多人是被"三数之和"这道题第一次卡住的。它看起来人畜无害——"找出数组中所有不重复的三元组，使得三数之和为 0"——比两数之和只多了一个数，结果暴力解超时，哈希解去重去得头皮发麻，一看题解又全是"排序 + 双指针"这套话术。作为 Java 刷题选手，这道题我前前后后写了三版才彻底吃透。这篇就来完整拆解一下双指针解法的推导过程、Java 实现细节，以及那些题解里不会明说但实测一定会踩的坑。无论你是刚开始刷 Hot 100，还是面试前突击双指针题目，这篇都值得你花十分钟慢慢看。

1. 为什么 Hot 100 里的三数之和值得单独写一篇

1.1 一道"入门级困难题"的尴尬定位

力扣的 Hot 100 选题其实很有讲究，它不按难度均匀分布，而是按"这道题在面试里出现的频率、覆盖的算法思想、以及能不能形成知识迁移"来选。三数之和能被放进 Hot 100，并且长期霸占题目列表靠前的位置，不是因为它的代码有多长、算法有多高深，而是因为它恰好卡在一个微妙的阈值上：暴力法太慢，哈希法太绕，双指针法需要你想清楚"排序到底带来了什么"。

我见过不少刷题群里的同学，两数之和做了三遍，三数之和就直接翻车。两数之和的经典做法是用哈希表记录"我还缺什么"，一次遍历就能搞定，时间复杂度 O(n)。到了三数之和，如果你顺着这个思路往下走，很容易想到"固定一个数，再用两数之和哈希去解决剩下两个数"，这样整体是 O(n²)，看上去很合理。但你真写起来就会发现，去重成了噩梦：数组里有重复元素，找到的组合也可能重复，哈希表里存三元组还得考虑顺序，最后要么用排序后拼接字符串做 key，要么用 Set 嵌套 Set，代码越写越长，性能还莫名变差了。

而我后来反复跟人强调的一个观点是：三数之和这道题，本质上是逼你放弃哈希思维，转入有序性思维。一旦你把数组排好序，哈希表的那套结构就完全不必要了，一个左指针配一个右指针，就能在线性时间里找到所有合法组合。这个思维转换，才是 Hot 100 把它放在数组类型题目中靠前位置的原因——它是一座桥，桥那边是四数之和、n 数之和、以及一切"固定若干个元素后双指针收缩"的题目。

1.2 这题真正在考什么

从面试官视角看，三数之和这道题考察的不是你能不能背出模板，而是三件事：

• 去重能力：题目明确要求"不重复的三元组"，这是一个很容易被忽略但很考察代码功底的点。很多候选人能写出 O(n²) 的算法，但去重逻辑写错，或者用 HashSet 暴力去重，面试官一眼就能看出你只是会背题，没有理解题。
• 双指针的状态管理：什么时候移动左指针，什么时候移动右指针，什么时候两个都动，什么时候要跳过重复值，这些细节一多，代码就乱。能把这些理清楚的人，写其他双指针题（接雨水、盛最多水的容器、四数之和）也不会太差。
• 对排序预处理的理解：为什么排序没有让这道题变成 O(n log n) 的负担？因为排序只做一次，后续的双指针收缩让每个固定元素只花费 O(n) 的时间，总复杂度仍然是 O(n²)，排序的 O(n log n) 只是低阶项。

所以说，这道题本质上不是"写出来"的题，而是"想明白"的题。下面我先把暴力和哈希这两条弯路走一遍，你会更清楚双指针好在哪里。

2. 暴力解法输在哪里：复杂度只是表面，去重才是要害

2.1 三重循环的规模感

先看大多数人第一反应会写的暴力解：

public List<List<Integer>> threeSum(int[] nums) { Set<List<Integer>> res = new HashSet<>(); int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] + nums[j] + nums[k] == 0) { List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]); Collections.sort(list); res.add(list); } } } } return new ArrayList<>(res); }

这段代码的写法是"先无脑枚举，再把每个三元组排序后塞进 Set 去重"。如果是数据量小（比如 n = 20），它一点问题都没有。但力扣这道题的数据范围是3 <= nums.length <= 3000，n 的三次方是 270 亿次计算量。即使每两次加法只花 1 纳秒，也要 27 秒往上，超时妥妥的。

但我想说的重点不是 O(n³) 慢，而是去重思路从根上就错了。当你还在用三重循环枚举时，去重只能靠"排序 + HashSet"这种事后补救的方式。可问题在于：同样的三元组 (a, b, c) 在数组里的位置组合可能有很多种，比如数组是[-1, 0, 1, -1, 2, -1]，[-1, 0, 1]这个组合会重复出现很多次，你每次都做一次排序、一次哈希计算、一次 Set 插入，这些操作的时间开销远超加法本身。

2.2 集合去重为什么在"返回组合"场景下很笨重

你可能会想：哈希表不是 O(1) 吗？确实，单次插入是 O(1)，但 O(n³) 个候选中可能有非常多的重复组合，而且每个组合要排序（O(3 log 3) 也是常数级）、要生成 List 对象、要算 hashCode，这些常数乘以 270 亿，谁也扛不住。更气人的是，Arrays.asList生成的 List 是基于数组的，哈希值计算要遍历元素，再加上 Set 内部维护红黑树或链表结构，整体开销被灾难性放大了。

有些经验丰富的同学会改用"固定第一个数 + 哈希表找两数之和"的 O(n²) 解法，思路大概是这样：

for (int i = 0; i < n; i++) { Map<Integer, Integer> map = new HashMap<>(); for (int j = i + 1; j < n; j++) { int target = -nums[i] - nums[j]; if (map.containsKey(target)) { // 找到一个组合 } map.put(nums[j], j); } }

这个写法的时间复杂度确实降低到了 O(n²)，但它有一个致命伤——去重逻辑散落在各处：外层i要跳过重复值，内层找到的(target, nums[j])组合也可能重复，而且你准备好的 Set 依然要对三元组做排序去重。也就是说，哈希解法在"判断是否存在"的场景下非常优雅，但在"输出所有不重复组合"的场景下，它的去重成本完全不比暴力低，代码还更难读。

我第一次在面试里写哈希版本的时候，写到去重那一步就卡壳了。面试官很善意地提醒了一句："你为什么不先排序呢？" 那一刻我才突然意识到：这题的题眼不是"和为零"，而是"有序数组能用双指针压缩搜索空间"。由此才有了下文这套经典解法。

3. 双指针怎么想出来的：从两数之和到三数之和的推导

3.1 排序给搜索空间带来了什么

先看一个更基础的子问题：在有序数组中，找出所有两数之和等于target的不重复组合。比如arr = [-4, -1, -1, 0, 1, 2]，要找两数之和等于 -1 的所有组合。

如果你用双重循环，要做 15 次比较。但如果用双指针：

• 左指针left指向数组最左端（最小值），右指针right指向最右端（最大值）。
• 计算arr[left] + arr[right]：
  • 如果和等于 target，找到一组；
  • 如果和小于 target，说明当前左边的数太小了，左指针右移（增大加数）；
  • 如果和大于 target，说明当前右边的数太大了，右指针左移（减小加数）。

关键在于，为什么可以放心移动指针？这背后的单调性是排序赋予的：left往右移动时，arr[left] + arr[right]之和单调不减（因为left增大，right不动）；right往左移动时，和单调不增。于是，每一轮比较都排除掉了一整批不可能产生目标和的组合，搜索空间被压缩成一条线，时间复杂度从 O(n²) 降到 O(n)。

这个子问题你可以直接迁移到三数之和上：先固定一个数nums[i]，剩下两个数的目标就是-nums[i]，再对剩下的子数组做双指针两数之和。

3.2 左右指针收缩为什么不会漏解

很多人第一次学双指针时都会有个疑惑：你只移动比大小的一边，万一正确答案里需要的数被跳过了怎么办？我用一个非常直观的方式来解释。

假设固定了nums[i]，子数组是nums[left..right]，并且它已经有序。我们比较nums[left] + nums[right]和target的大小。如果和小于 target，因为nums[right]已经是当前范围内最大的数了，nums[left]与它相加都小于 target，那nums[left]与任何其他右边的数相加只会更小于 target。换言之，nums[left]这个数已经"不可能"参与任何一组合法解了，放心把left右移即可。反过来，如果和大于 target，因为nums[left]是当前范围内最小的数，它跟nums[right]相加都大于 target，那nums[right]跟任何其他左边的数相加只会更大，所以nums[right]也可以被放弃了，right左移即可。

"和比目标小，移动左指针；和比目标大，移动右指针"这条规则，本质上就是在每一轮都排除一个当前确定无用的元素。所有可能合法的组合都在被不断缩小的区间里，直到两个指针相遇。因此这是一个不会漏解的正确算法——它不是靠运气碰，而是靠单调性做排除。

3.3 从两数之和到三数之和的落地思路

有了上面的基础，三数之和的算法骨架就非常清晰了：

1. 先把整个数组排序。
2. 外层用一个for循环固定第一个数nums[i]，它的取值范围是从 0 到n - 3（至少要给后面留两个位置）。
3. 内层问题变为：在nums[i+1..n-1]这个有序子数组中，找所有两数之和等于-nums[i]的组合，用左右双指针实现。
4. 注意去重：外层固定的值不能重复；内层找到一个组合后，左右指针都要跳过与自己相同的元素。

这个结构可以理解为"排列组合意义上的剪枝"：外层for决定第一个元素是谁，内层双指针决定后两个元素是谁。由于数组有序，且内层也是通过指针收缩而不是枚举去搜索，整个过程没有冗余的组合尝试。

顺带说一句，如果你对两数之和只记得"哈希表"这一种解法，我建议你把"有序数组双指针求两数之和"也练熟。它不只在三数之和里有用，在"盛最多水的容器""接雨水"这些题目里也是核心工具，早学会早受益。

4. Java 标准解法：代码、去重、剪枝逐段拆解

4.1 完整代码先放在这里

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; if (n < 3) { return res; } Arrays.sort(nums); for (int i = 0; i < n - 2; i++) { if (nums[i] > 0) { break; } if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = n - 1; int target = -nums[i]; while (left < right) { int sum = nums[left] + nums[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } } } return res; } }

这段代码是所有 Hot 100 题解里最主流的写法，我也建议你直接把它背到肌肉记忆里。但背之前，我想把每一处的"为什么"讲透。

4.2 三个关键去重点

第一个去重点在外层，也就是if (i > 0 && nums[i] == nums[i - 1]) { continue; }。它的意思是：当前固定的第一个数，如果和前一个固定的数相同，那就跳过。这很好理解——同一个值已经在前面固定过一次，内层双指针对应的目标也完全相同，再固定一次只会产出重复的三元组。

这里有一个很多新手都会写错的细节：有人会把判断写成if (nums[i] == nums[i + 1]) continue;，这是错的。假设数组是[-1, -1, 2]，正确答案应该有一个[-1, -1, 2]组合。如果裁判条件是nums[i] == nums[i + 1]，当i = 0时nums[0] == nums[1]成立，直接continue跳过了，唯一的合法组合就丢了。我们要跳过的是"已经用过这个值作为第一个数"的情况，所以必须和nums[i - 1]比较，而不是和nums[i + 1]比较。这是一个非常经典的边界逻辑，面试官很喜欢在这里挖坑。

第二个去重点在内层找到合法组合之后：

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

找到sum == target的组合后，left和right当前对应的两个数已经被记录进答案了，后面如果还遇到相同的nums[left]或nums[right]，组合就重复了。所以先把左右指针移动到相邻值不相等的位置，然后再left++、right--进入下一轮探测。

第三个去重点其实就是前两个的组合效果：外层去重保证"第一个数"不重复，内层去重保证"在同一个第一个数下，后两个数不重复"。三者配合，输出结果天然无重，不需要任何 Set。

4.3 两类剪枝：提前终止和跳过无望的固定值

代码里有一个if (nums[i] > 0) break;。因为数组已经从小到大排序，如果当前固定的nums[i]都大于 0 了，那它右边的数也都大于 0，三个正数相加无论如何不可能等于 0，后面都不用看了，直接结束整个循环。这是本题里最常用的剪枝，效率提升也很明显。

另外还有一个常见但很多人不知道的剪枝，我补在下面，你可以作为优化参考：

// 如果当前最小的三个数之和都大于 0，直接退出 if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break; // 如果当前数加上最大的两个数仍小于 0，说明当前数太小了，跳过 if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;

第一个剪枝的逻辑是：nums[i]是剩余数组里的最小三个数的起点，这三个数最小都大于 target 了，后续再没有任何组合能达到目标。第二个剪枝的逻辑是：nums[i]已经很小了，即使跟整个剩余部分里最大的两个数相加都小于 0，那它和任何其他组合都不可能凑成 0，直接换下一个i。这两个剪枝在数据分布极端（比如全是正数、全是负数）时能把性能提升不少，面试中主动提出来也会加分。但要注意，加剪枝不能改变算法正确性——比如剪枝后还要保证不会误跳过合法答案，上面这两个条件是严格安全的。

4.4 复杂度与暴力法的直观对比

这里的空间复杂度要说明一下：Arrays.sort(int[])在 Java 中用的是双轴快排，递归栈平均空间 O(log n)。如果你实现的是原地排序的变体，那额外空间可以认为是 O(1)。输出结果占用的List空间不算在算法辅助空间内。

5. 实测最容易翻车的地方：重复解、死循环、边界与溢出

5.1 数组长度不足与排序后指针初始化的边界

最基本的边界是n < 3：数组里一共就两三个元素，不可能凑出三元组，直接返回空列表。很多人会忽略这一点，结果排序之后for循环里i < n - 2直接越界，或者left = i + 1指到了数组外面。写上这个检查只需要一行，别省。

其次，外层循环的条件是i < n - 2，不是i < n。原因很简单：固定第一个数后，至少要给左指针和右指针各留一个位置。如果你写成i < n，到i = n - 1时left = n，right = n - 1，本来就不满足left < right，虽然不会报错，但白白多跑几次无意义的循环。

5.2 相等分支里的"跳重"为什么不做就会重复

我用一个具体例子说明。假设排序后的数组是[-2, 0, 0, 2, 2]。外层固定i = 0，也就是-2，目标target = 2。这时left = 1（指向 0），right = 4（指向 2）。

• 第一次循环：nums[1] + nums[4] = 0 + 2 = 2，正好等于 target，记录[-2, 0, 2]。
• 此时如果只left++和right--一次，left = 2（仍然指向 0），right = 3（仍然指向 2），又得到一组[-2, 0, 2]，答案重复了。
• 加上两个while跳重后，left会从 1 跳到 2（0 == 0，跳过），再跳到 3（0 != 2，停止）；right从 4 跳到 3（2 == 2，跳过），再跳到 2（2 != 0，停止）。这时left = 3，right = 2，已经不满足left < right了，自然退出内层循环，完美避开重复。

如果不跳重，这道题在样例数据里就会输出重复的三元组，直接判错。这也是我见过的最高频的提交错误。

5.3 sum 的溢出和 LeetCode 数据范围

很多老题解里写的是int sum = nums[i] + nums[left] + nums[right]，然后用 sum 和 0 比较。这在当前力扣版本的数据范围下（nums[i]绝对值不超过 10^5）不会溢出，因为三个数之和的绝对值最大是 3 * 10^5，远小于Integer.MAX_VALUE。

但你如果是在面试手写代码，面试官很可能会问你："如果数组里的数可以到 10^9 呢？" 这时候三个 int 相加就可能溢出，稳妥的写法是提前移项，比较nums[left] + nums[right]与-nums[i]，或者直接用long。我建议你在代码里一开始就写成：

int sum = nums[left] + nums[right]; if (sum < -nums[i]) { left++; } else if (sum > -nums[i]) { right--; } else { // 找到组合 }

这样既回避了三数相加溢出的问题，语义也更清楚：内层就是在做"两数之和等于目标的相反数"。等到你写四数之和的时候，这个思维习惯会让你少踩一个很大的坑（四数之和里四个 int 相加更容易溢出，力扣官方用例里甚至专门准备了超 int 的边界测试）。

5.4 死循环与指针更新不到位

再提醒一个新手常犯的错：在sum == target这个分支里，如果你只写了一边跳重（比如只 skip 左指针重复，不 skip 右指针重复），然后执行left++、right--，大多数情况下也能凑合运行，但偶尔会因为左右指针移动后正好又撞上重复值，导致死循环。我建议把两个while都写上，并且保证在 while 之后还有一次left++和right--。这两个 while 只是把指针移到"最后一个重复值"的位置，不带最后的left++/right--，指针就永远不会越过重复区间，内层循环会卡死。

6. 一题打通一类：四数之和、n 数之和到底在考什么

6.1 从三数到四数，只是多套了一层循环

三数之和吃透之后，四数之和基本就是照葫芦画瓢：排序，固定前两个数（用两层 for 循环），剩下的两个数继续用双指针收缩。去重逻辑对应也要加一个位置——第二个固定数的去重。时间复杂度从 O(n²) 变成 O(n³)，但代码骨架几乎一模一样。

public List<List<Integer>> fourSum(int[] nums, long target) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; if (n < 4) return res; Arrays.sort(nums); for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; int left = j + 1, right = n - 1; while (left < right) { long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < target) { left++; } else { right--; } } } } return res; }

可以看到，核心思想一点没变。所谓"n 数之和"，就是先排序，然后固定 k-2 个数（k 层循环），最后两个数用双指针，时间复杂度 O(n^(k-1))。理解了这一点，你在面试里遇到"五数之和"也不会慌，直接往这个模板上套。

6.2 面试官追问的进阶问题

我整理了一下面试中围绕这道题我最常被追问的问题，你也可以拿来自测：

• "如果只要判断是否存在，不用返回具体组合，能优化吗？"可以。用哈希表记录两数之和，再遍历找相反数，期望时间复杂度 O(n²)，但不需要维护去重结构。不过严格说，要"判断是否存在"时哈希表比双指针更灵活，因为它不需要排序，适合数组不能改动的场景。
• "如果数组非常大，不能整体排序怎么办？"那双指针就失效了，只能退回到"固定一个数 + 哈希表"的思路，或者用分治/外部排序的方式先处理数据。面试里大概率是考察你对排序前置条件的理解。
• "为什么这题不用哈希表而要排序？"因为题目要求返回所有不重复组合。排序可以让"重复元素相邻"，配合指针跳重，去重逻辑变得非常简单；哈希表在去重时的代价远高于排序。
• "如果目标值不是 0 呢？"把内层目标从-nums[i]换成target - nums[i]即可，其余逻辑完全不用改。四数之和题目的目标值确实可以是任意整数。

这几个追问能答上来，说明你不是背的模板，而是真的理解了双指针在有序数组上收缩的原理。

7. 刷完三数之和，我最想留下的几条经验

刷题这件事，最怕的是"背了模板却不理解原理"。三数之和我刷了三遍，每一遍都有新收获，这里说几条我后来一直沿用的经验。

第一，看到"子数组/组合/配对"这类词，先想想能不能排序。排序不是只能让数据变好看，它会给数组赋予单调性，而单调性是双指针、二分法的基础。很多题目的最优解都由"排序 + 某种有序性搜索"构成。

第二，去重逻辑一定放在"产出答案的路径上"，而不是产出之后再用 Set 过滤。三数之和里，外层去重放在固定值入口，内层去重放在找到组合之后，三条去重规则各自负责一个维度。这样的代码效率高、逻辑清晰，也更容易向面试官解释。

第三，指针一切要"跳到位"。每次跳过重复值的 while 循环都要把指针移动到"最后一个重复值"的位置，然后再left++/right--，跳过一个完整的重复区间。这个细节我至少见过十几个同学在代码里栽过跟头，运行起来要么死循环，要么答案重复。

第四，如果时间允许，把这题的变体也刷一遍：两数之和（有序版）、三数之和（最接近）、四数之和。你会发现，每刷一道，对"固定若干元素 + 双指针收缩"这个模式的理解就会深一分。Hot 100 里这类题目是成体系出现的，吃透一个，相当于解锁一整片。

最后再说一句掏心窝的话：遇到像三数之和这种"看似简单、实则刁钻"的题，别急着看题解，先自己试错一轮。把暴力解法写出来、跑一遍、看它怎么超时，再想怎么用有序性优化——这个过程比你背十道题解都值钱。至少对我来说，就是那次面试被提醒"为什么不先排序"之后，我才真正打开了双指针这扇门。