三数之和怎么做？为什么先排序再用双指针？如何去重？
简化版
找出数组里所有和为 0 的三元组。做法:先排序,然后固定一个数 nums[i],在它右边用对撞指针找两数之和 = -nums[i]。排序把 O(n³) 的暴力枚举降到 O(n²)(外层固定 i 是 O(n),内层双指针 O(n))。去重是难点:要跳过重复的 i、以及找到一组解后跳过重复的 left/right,避免输出重复三元组。
详细版
List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 1. 排序
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break; // 最小的都 > 0，不可能凑出 0
if (i > 0 && nums[i] == nums[i-1]) continue; // 跳过重复的 i
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
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--;
} else if (sum < 0) left++; // 和太小，左指针右移
else right--; // 和太大，右指针左移
}
}
return res;
}排序 O(n log n) + 主体 O(n²) = O(n²);去重靠三处「跳过相邻相等」。
完整版教学
一、为什么先排序
暴力解法是三重循环枚举所有三元组,O(n³)。排序带来两个关键好处:
- 能用对撞指针:排序后数组有序,固定一个数后,剩下「找两数之和等于某值」就能用 O(n) 的对撞指针(而不是 O(n²) 的嵌套或哈希),把总复杂度降到 O(n²)。
- 方便去重:排序后相同的数会相邻,去重只需「跳过和前一个相等的元素」,非常简单。如果不排序,去重要用 Set 存三元组,麻烦且慢。
所以「排序 + 对撞指针」是三数之和的标准框架。
二、核心结构:固定一个 + 双指针找两个
把三数之和 a + b + c = 0 转化为:固定 a = nums[i],在 i 右边的有序区间里找 b + c = -a。这正是「有序数组两数之和」——用对撞指针 left、right:
sum < 0→ 需要更大的和 →left++。sum > 0→ 需要更小的和 →right--。sum == 0→ 记录这组解,然后两个指针都向内移动继续找。
外层 O(n) 遍历固定数,内层 O(n) 双指针,总 O(n²)。
三、去重的三个地方(重点,最易错)
三数之和最容易出错的就是去重——要保证输出的三元组不重复。三个地方都要处理:
- 固定数 i 去重:
if (i > 0 && nums[i] == nums[i-1]) continue;——如果当前nums[i]和上一个相同,它能组成的三元组上一轮已经找过了,跳过。注意是和i-1比(前一个),不是i+1,否则会漏掉合法的重复(如[0,0,0])。 - 找到解后 left 去重:
while (nums[left] == nums[left+1]) left++;——跳过和当前left相同的,避免重复三元组。 - 找到解后 right 去重:
while (nums[right] == nums[right-1]) right--;——同理跳过重复的 right。
只有三处都去重,才能保证结果无重复。这是本题的核心考点。
四、剪枝优化
排序后可以加剪枝加速:
if (nums[i] > 0) break;:数组已排序,如果最小的固定数nums[i]都大于 0,那三个正数之和不可能是 0,后面更大,直接结束。- 类似地,可以判断
nums[i] + nums[i+1] + nums[i+2] > 0直接 break、nums[i] + nums[n-1] + nums[n-2] < 0就continue,进一步剪枝。
剪枝必须建立在升序数组上，并且只能排除整段不可能产生 0 的候选。第一条最小和已经大于 0 时后续只会更大；第二条最大和仍小于 0 时当前 i 无解，但后续更大的 i 仍可能有解，所以只能 continue，不能 break。
五、走一个例子
nums = [-1, 0, 1, 2, -1, -4]
排序后: [-4, -1, -1, 0, 1, 2]
i=0(-4): left,right 找和=4,无解
i=1(-1): 找和=1 → (-1,0,1)? left=2(-1)... 找到 (-1,-1,2) 和 (-1,0,1)
i=2(-1): 和 i=1 相同 → 跳过（去重）
结果: [[-1,-1,2], [-1,0,1]]六、复杂度与延伸
- 时间 O(n²):排序 O(n log n) + 主体 O(n²)。
- 空间 O(1)(不算结果和排序栈)。
- 延伸:
- 四数之和:再套一层固定,变成固定两个 + 双指针,O(n³)。
- 最接近的三数之和:同样框架,记录最接近 target 的和。
- 三数之和 = target(非 0):把
-nums[i]换成target - nums[i]。
七、把不变量、推演与工程边界落到代码上
算法正确性的核心不是记住某个 while，而是始终维护这个不变量：排序后固定 i，左右指针在剩余有序区间中只排除不可能的和。
对应的状态推进是：sum<0 左移，sum>0 右移，命中后三处都要跳过重复值。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。
初始化边界与状态
while 尚未结束:
根据当前状态作出唯一可证明安全的选择
更新边界、计数或局部结构
断言不变量仍然成立
返回不变量在终止状态下推出的答案复杂度不能只背一个符号。排序 O(n log n)，外层 n 次线性夹逼使总时间 O(n²)。
带数字走一遍：[-1,0,1,2,-1,-4] 排序后得到 [-1,-1,0,1,2] 与 [-1,0,1]。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。
| 核对项 | 结论 |
|---|---|
| 前提 | 输出通常要求不重复三元组；值和可能需要 long 防溢出 |
| 时间复杂度 | O(n²) |
| 额外空间 | 除排序栈外 O(1)，不计结果 |
| 关键边界 | i 与命中后的 left/right 都要去重；i>0 且 a[i]>0 可提前结束 |
| 替代方案 | 两数之和有序版是其内层；k-sum 可递归降维 |
易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。
实现完成后至少检查五类用例：
- 空输入或题目允许的最小规模，验证初始化不会越界。
- 单元素与两个元素，验证循环条件和最后一次推进。
- 大量重复值，验证相等分支、稳定性或去重语义。
- 已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
- 上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。
八、常见误区与追问
- 误区：只要记住模板就适用于所有输入。 本题成立的前提是“输出通常要求不重复三元组；值和可能需要 long 防溢出”，前提被破坏后必须换算法或重新证明。
- 误区：复杂度只写 O(n²) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“排序 O(n log n)，外层 n 次线性夹逼使总时间 O(n²)”。
- 误区：重复值和边界值不会改变代码。 i 与命中后的 left/right 都要去重；i>0 且 a[i]>0 可提前结束。
- 追问：为什么每次推进不会漏掉答案？ 因为始终维护“排序后固定 i，左右指针在剩余有序区间中只排除不可能的和”，被舍弃区域已由顺序或状态关系证明不可能更优。
- 追问：用一个数字例子怎么讲？ 可以从“[-1,0,1,2,-1,-4] 排序后得到 [-1,-1,0,1,2] 与 [-1,0,1]”开始，逐轮写出状态与被排除区间。
- 追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“两数之和有序版是其内层；k-sum 可递归降维”。
- 追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。
九、加强记忆
三数之和:先排序,再固定 nums[i]、在右边用对撞指针找两数之和 = -nums[i],O(n²)(排序让暴力 O(n³) 降一阶,还方便去重)。去重是核心,三处都要:固定数和 i-1 比跳过、找到解后 left/right 各跳过相邻相等。剪枝:nums[i]>0 直接 break。延伸到四数之和(再固定一层)、最接近三数之和(记录最接近)。