双指针专题(三)：去重的艺术——「三数之和」
哈喽各位，我是前端小L。
场景想象：
给你一个数组 [-1, 0, 1, 2, -1, -4]。
我们要找出所有和为 0 的三个数 [a, b, c]。
我们可以找到
[-1, 0, 1]。还可以找到
[-1, 2, -1]（排序后是[-1, -1, 2]）。难点：数组里有两个
-1，如果我们不加控制，代码很可能会把第一个-1开头的[-1, 0, 1]算一次，再把第二个-1开头的[-1, 0, 1]又算一次。这就是重复。
力扣 15. 三数之和
https://leetcode.cn/problems/3sum/
题目分析：
输入：整数数组
nums。输出：所有和为 0 的不重复三元组。
复杂度要求：暴力法是 $O(N^3)$，肯定超时。我们需要优化到$O(N^2)$。
核心思维：排序 + 固定一个，找另外两个
既然双指针擅长解决“两数之和”，那我们能不能把“三数之和”降维打击？
策略：
先排序：这是去重和使用双指针的前提！(例如
[-4, -1, -1, 0, 1, 2])。遍历固定位 (
i)：我们遍历数组，固定第一个数nums[i]。双指针找两数：剩下的问题就变成了——“在
i后面的数组中，找到两个数Left和Right，使得nums[Left] + nums[Right] = -nums[i]”。
去重逻辑（最关键）：
外层去重（针对 i）：
如果 nums[i] === nums[i-1]，说明这个数刚才已经作为“第一个数”处理过了，再处理一遍肯定会得到一样的结果。跳过！
内层去重（针对 Left 和 Right）：
当我们找到了一个合法的组合后，如果 nums[Left] === nums[Left+1]，说明下一个数还是一样，会导致结果重复。跳过！ 右边同理。
算法流程 (JavaScript)
排序：
nums.sort((a, b) => a - b)。外层循环：
i从0到n-2。如果
nums[i] > 0：因为已经排序，第一个数大于0，后面不可能凑出 0 了，直接break。去重：
if (i > 0 && nums[i] === nums[i - 1]) continue;双指针启动：
L = i + 1,R = n - 1。计算
sum = nums[i] + nums[L] + nums[R]。sum > 0：数太大了，R往左移。sum < 0：数太小了，L往右移。sum === 0：记录答案：
res.push([nums[i], nums[L], nums[R]])。内层去重：
while (L < R && nums[L] === nums[L+1]) L++;(跳过重复的L)内层去重：
while (L < R && nums[R] === nums[R-1]) R--;(跳过重复的R)双双移动：
L++,R--(寻找下一组)。
代码实现
JavaScript
/** * @param {number[]} nums * @return {number[][]} */ var threeSum = function(nums) { const result = []; // 1. 必须排序 nums.sort((a, b) => a - b); const len = nums.length; for (let i = 0; i < len; i++) { // 剪枝：如果第一个数已经大于0，后面都是正数，不可能凑成0 if (nums[i] > 0) break; // 2. 外层去重：如果我们遇到了和上一次一样的数字，跳过 // 注意是 i > 0，防止 i-1 越界 if (i > 0 && nums[i] === nums[i - 1]) continue; let L = i + 1; let R = len - 1; while (L < R) { const sum = nums[i] + nums[L] + nums[R]; if (sum === 0) { // 找到一组，加入结果 result.push([nums[i], nums[L], nums[R]]); // 3. 内层去重：找到答案后，看看左右指针旁边是不是有重复的 // 如果有，一直跳过，直到指向最后一个重复元素的下一位 while (L < R && nums[L] === nums[L + 1]) L++; while (L < R && nums[R] === nums[R - 1]) R--; // 找到答案后，两个指针都要收缩 L++; R--; } else if (sum < 0) { // 和太小，左指针右移变大 L++; } else { // sum > 0 // 和太大，右指针左移变小 R--; } } } return result; };深度辨析：为什么去重是nums[i] === nums[i-1]？
很多同学会纠结：是判断nums[i] == nums[i-1]还是nums[i] == nums[i+1]？
情况 A (nums[i] == nums[i-1])：
比如 [-1, -1, 2]。
i=0(第一个 -1)：处理一遍，找到了[-1, -1, 2]。i=1(第二个 -1)：我们回头看，发现前一个也是 -1。如果我们再处理，就会重复寻找。所以跳过。这是正确的逻辑：只要我前面那个“长得跟我一样”的兄弟已经处理过了，我就不用再处理了。
情况 B (nums[i] == nums[i+1])：
如果我们判断的是后一个。
i=0(第一个 -1)：发现后面也是 -1，直接跳过？错！这样你就漏掉了
[-1, -1, 2]这一组情况（这组情况需要用到两个 -1）。结论：我们去重的是“作为第一个加数的重复”，而不是禁止三元组内部有重复数字。
总结
这道题是双指针的里程碑。
掌握了它，你就掌握了 “排序 + 降维 + 双指针夹逼 + 细致去重” 的完整套路。
下一题预告：四数之和
如果面试官觉得三数之和太简单，可能会随手丢给你一道LC 18. 四数之和。
题目：找到
a + b + c + d = target。思路：套娃。
三数之和是：固定
i，算两数之和。四数之和是：固定
k，再固定i，算两数之和。
难点：多了一层循环，也就多了一层剪枝和去重的逻辑。
准备好再加一层循环了吗？下期见！