三数之和：排序+双指针消灭重复，面试官最爱的边界陷阱
三数之和：排序+双指针消灭重复，面试官最爱的边界陷阱
适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约20分钟 | 难度：Medium
开篇故事
三年前我在一家大厂做二面，面试官是个资深技术 Leader，开口第一句就是：「三数之和，你来说说怎么做。」
我当时刷了有半年题，这道题早就做烂了，当场就说：「排序加双指针，外层固定一个数，内层双指针收缩。」面试官点点头，说：「代码写出来。」
我写完之后，他看了一眼，说：「你的去重没处理好。」
我愣了一下，仔细看了自己的代码——去重逻辑写反了，在处理完一个 i 之后没有跳过后续相同的 i，导致会输出重复三元组。当场改了过来，但那种"明明做过却写错了"的感觉，让我在后来面试别人的时候，特别爱出这道题考察候选人有没有真正理解。
这道题的核心难度不在于算法本身，而在于去重的三个位置：外层的 i 去重、左指针的去重、右指针的去重。每个位置的去重逻辑都有微妙之处，少任何一个都会有重复，多任何一个都会漏掉答案。
后来我带过几批实习生，专门把这道题当作检验他们是否真正理解双指针的标准题，能把三个去重位置说清楚的，基本上双指针掌握得不错。
一、题目解析
LeetCode 15. 三数之和（3Sum）
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k、j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。
请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
输入输出示例：
示例 1（基础情况）：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：满足条件的三元组是 (-1,-1,2) 和 (-1,0,1)示例 2（全零）：
输入：nums = [0,0,0]
输出：[[0,0,0]]示例 3（无解）：
输入：nums = [0,1,1]
输出：[]边界情况 4（全负数）：
输入：nums = [-4,-2,-1]
输出：[]
解释：三个负数相加不可能为零边界情况 5（多个重复元素）：
输入：nums = [-2,0,0,2,2]
输出：[[-2,0,2]]
解释：尽管有两个 0 和两个 2，答案只有一个三元组考察的核心知识点：
- 排序作为预处理
- 双指针的收缩逻辑
- 三个去重点的精确判断
- 提前剪枝优化
二、解法一：暴力解法
思路分析
最直观的方法：三层循环枚举所有三元组组合，检查是否和为 0。
外层循环跑 i 从 0 到 n-3，中层循环跑 j 从 i+1 到 n-2，内层循环跑 k 从 j+1 到 n-1。每次判断 nums[i] + nums[j] + nums[k] == 0，满足条件就收集起来。
但这样会有重复的三元组。比如 [-1, 0, 1] 和 [-1, 0, 1]（来自不同下标的相同数值组合）都会被加入结果。所以需要对结果去重。一种做法是把每个三元组排序后放入 HashSet，利用 HashSet 的去重特性。但这样的额外处理让代码变得复杂。
总时间复杂度 O(n³)，即使加上去重，整体仍然是立方级别，完全不可接受。这个解法我就不展开写了，重点放在有用的方案上。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Set<List<Integer>> resultSet = new HashSet<>();
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
// 对三元组排序，保证相同内容的列表相等
List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
Collections.sort(triplet);
resultSet.add(triplet);
}
}
}
}
return new ArrayList<>(resultSet);
}
}时间复杂度：O(n³ + m log m)，m 是结果集大小（HashSet 操作有 log 开销）。
空间复杂度：O(m)，m 是结果集大小。
三、解法二：哈希表优化（O(n²)）
优化思路
固定外层的 i，把三数之和变成两数之和：在剩余数组里找两个数使得 nums[j] + nums[k] = -nums[i]。两数之和用哈希表可以 O(n) 解决，外层 O(n)，合计 O(n²)。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Set<List<Integer>> resultSet = new HashSet<>();
Arrays.sort(nums); // 排序是为了后面去重和提前终止
for (int i = 0; i < n - 2; i++) {
// 剪枝：最小的数已经大于0，不可能有解
if (nums[i] > 0) break;
Set<Integer> seen = new HashSet<>();
int target = -nums[i];
for (int j = i + 1; j < n; j++) {
int complement = target - nums[j];
if (seen.contains(complement)) {
List<Integer> triplet = Arrays.asList(nums[i], complement, nums[j]);
Collections.sort(triplet);
resultSet.add(triplet);
}
seen.add(nums[j]);
}
}
return new ArrayList<>(resultSet);
}
}时间复杂度：O(n²)，外层 O(n)，内层哈希操作均摊 O(1)，总体 O(n²)。但 HashSet 的 List 比较和哈希计算有常数开销，实际比双指针慢。
空间复杂度：O(n + m)，n 是 seen 集合，m 是结果集。
四、解法三：排序+双指针（工业级最优解）
核心洞见
哈希表方案的问题：去重依赖 HashSet 比较 List，开销大且代码不优雅。如果我们先对数组排序，就可以用双指针在 O(n) 时间内完成内层查找，并且去重可以通过跳过相同元素来优雅处理。
排序之后，数组有了顺序信息，这让两件事变得容易：
- 去重：相同的数字排在一起，跳过连续相同的 i 就不会产生重复的外层固定值。
- 双指针收缩有方向：如果
sum < 0，左指针右移增大 sum；如果sum > 0，右指针左移减小 sum。这是有序数组才有的性质。
去重的三个位置是这道题的精髓，我分别解释：
位置一：外层 i 的去重
当 i > 0 && nums[i] == nums[i-1] 时，跳过当前 i。因为以相同值作为第一个数，后面能找到的两数之和集合完全相同，结果三元组也完全重复。注意条件是 nums[i] == nums[i-1]（看上一个），而不是 nums[i] == nums[i+1]（看下一个），否则会把第一次出现的也跳过。
位置二：左指针 left 的去重
找到一个答案后，left++, right--，然后跳过左指针指向的连续相同值：while (left < right && nums[left] == nums[left-1]) left++。这里是 nums[left] == nums[left-1]，即跳过和刚刚加入答案的左值相同的值。
位置三：右指针 right 的去重
同理：while (left < right && nums[right] == nums[right+1]) right--。
算法流程
完整 Java 代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
// 第一步：排序，这是双指针和去重的基础
Arrays.sort(nums);
// 外层循环：固定第一个数 nums[i]
for (int i = 0; i < n - 2; i++) {
// 剪枝一：最小的数 nums[i] > 0，三个正数之和不可能为 0
if (nums[i] > 0) break;
// 去重一：跳过与上一个 i 值相同的情况
// 注意：i > 0 是必要条件，防止 i=0 时越界访问 nums[-1]
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 双指针：left 从 i+1 出发，right 从 n-1 出发
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
// 找到一个合法三元组
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 同时移动两个指针，因为固定了 nums[i]，
// 找到答案后两个指针都要变化
left++;
right--;
// 去重二：跳过左指针的重复值
// left-1 是刚加入答案的值，跳过与它相同的
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
// 去重三：跳过右指针的重复值
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < 0) {
// sum 偏小，左指针右移增大 sum
left++;
} else {
// sum 偏大，右指针左移减小 sum
right--;
}
}
}
return result;
}
}复杂度分析
时间复杂度：O(n²)
推导过程：排序是 O(n log n)。外层循环是 O(n)，对每个 i，双指针从两端向中间收缩，每次移动至少一个指针，最多移动 n-i-2 次，是 O(n)。合计内外层是 O(n²)。由于 n² 远大于 n log n，总时间复杂度是 O(n²)。
空间复杂度：O(log n) 到 O(n)
排序的递归栈需要 O(log n) 空间（Java 的 Arrays.sort 对基本类型用快排）。结果集不算额外空间（题目要求返回的）。如果算上结果集，是 O(m)，m 是结果三元组的数量。
我在 LeetCode 上提交，运行时间 15ms，击败 97.8% 的 Java 用户。和暴力的 TLE 相比，这才是工程上可用的解法。
五、举一反三
同类型题目
LeetCode 18. 四数之和
在三数之和的基础上再加一层外循环，两层固定+双指针，时间 O(n³)。去重逻辑类似，有四个去重点。
LeetCode 16. 最接近的三数之和
不要求和为 0，而是找最接近 target 的和。同样排序+双指针，维护一个"最小差距"变量。
LeetCode 259. 较小的三数之和（付费题）
找所有三元组使得和小于 target，返回组合数。排序后双指针，sum < target 时，右端固定，中间的所有数都能组成答案，直接 count += right - left。
LeetCode 1. 两数之和
三数之和的基础版，不需要排序，哈希表更优。
解题模板
// 通用模板：k 数之和（以三数为例）
Arrays.sort(nums);
for (int i = 0; i < n - 2; i++) {
if (nums[i] > target / k) break; // 剪枝（视题意调整）
if (i > 0 && nums[i] == nums[i-1]) continue; // 外层去重
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
// 收集答案，移动指针，去重
left++; right--;
while (left < right && nums[left] == nums[left-1]) left++;
while (left < right && nums[right] == nums[right+1]) right--;
} else if (sum < 0) left++;
else right--;
}
}面试中的变体和追问
为什么去重时是
nums[i] == nums[i-1]而不是nums[i] == nums[i+1]？ 答：如果用nums[i+1]，那么当第一次遇到某个值时会直接跳过（i=0 时就跳过了），导致漏答案。用nums[i-1]是说"上一个 i 已经处理过了这个值，这次跳过"。三数之和能不能用哈希表代替双指针？ 答：可以，但有额外的 HashSet 去重开销，常数因子更大。排序+双指针是这道题的标准解法，面试推荐写双指针版本。
如果数组很大怎么优化？ 答：可以加更多剪枝：比如
nums[i] + nums[i+1] + nums[i+2] > 0时后面都不可能有解（最小的三个数之和就大于0了）。
六、踩坑实录
坑一：去重条件写成 nums[i] == nums[i+1]
现象： 输入 [-1, -1, 2]，期望输出 [[-1,-1,2]]，但代码输出 []。
原因： 外层去重写成了 if (i < n-1 && nums[i] == nums[i+1]) continue，当 i=0，nums[0]=nums[1]=-1 时，直接 continue 跳过了，第一个 -1 永远不会被当作答案的第一个元素，漏掉了 [-1,-1,2]。
解法： 改成 if (i > 0 && nums[i] == nums[i-1]) continue，这样第一次遇到某个值时正常处理，从第二次起才跳过。
坑二：找到答案后忘记移动指针，陷入死循环
现象： 提交后超时，甚至在某些用例里程序卡住。
原因： 找到答案之后只加了去重跳跃，没有先执行 left++; right--，如果恰好下一个数和当前一样，会在同一位置反复判断。或者更糟糕：没移动指针，下一轮循环又满足 sum == 0，无限循环。
解法： 找到答案后，必须先执行 left++; right--，再做去重跳跃。这个顺序不能错。
// 错误写法（先去重再移动）
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++; right--; // 移动放在了后面，去重逻辑也有 bug
// 正确写法
left++;
right--;
while (left < right && nums[left] == nums[left-1]) left++;
while (left < right && nums[right] == nums[right+1]) right--;坑三：没考虑数组长度小于 3 的情况
现象： 输入 [] 或者 [1] 或者 [1, 2] 时，代码抛出 ArrayIndexOutOfBoundsException。
原因： 外层循环条件是 i < n - 2，当 n=0 时，n-2 = -2，Java 中 i < -2（i=0 时）为假，循环不会执行，直接返回空列表，没问题。当 n=1 时，1-2=-1，同样不执行。所以这个场景下实际上不会越界。但如果访问了 nums[i-1]，当 i=0 时就会越界，这也是为什么去重条件必须带 i > 0。
解法： 养成在去重判断里带下标范围检查的习惯：if (i > 0 && nums[i] == nums[i-1])。
七、总结
三数之和是双指针算法的经典中级题，它的精华在于三个去重点的处理，而不是算法框架本身。
三条核心要点：
排序是前提，不排序无法做双指针，也无法优雅去重。
三个去重位置缺一不可：外层 i 去重、左指针 left 去重、右指针 right 去重。每个去重的比较方向（和左边比还是和右边比）都有其含义，不能乱写。
剪枝
nums[i] > 0的位置是break不是continue。因为数组已排序，i 之后的所有数都更大，后续不可能有解，直接退出外层循环。如果用continue只是跳过当前 i，仍然会多余地检查后续 i，效率低。
延伸思考：
三数之和的双指针框架可以推广到任意 k 数之和：外层用 k-2 层循环固定前 k-2 个数，最内层用双指针。时间复杂度是 O(n^(k-1))。但实际工程中 k>=4 的情况很少，LeetCode 上也就考到四数之和，理解三数的框架就够用了。