滁州市网站建设_网站建设公司_搜索功能_seo优化

哈喽各位，我是前端小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)$。

核心思维：排序 + 固定一个，找另外两个

既然双指针擅长解决“两数之和”，那我们能不能把“三数之和”降维打击？

策略：

1. 先排序：这是去重和使用双指针的前提！(例如[-4, -1, -1, 0, 1, 2])。

2. 遍历固定位 (i)：我们遍历数组，固定第一个数nums[i]。

3. 双指针找两数：剩下的问题就变成了——“在i后面的数组中，找到两个数Left和Right，使得nums[Left] + nums[Right] = -nums[i]”。

去重逻辑（最关键）：

1. 外层去重（针对 i）：

   如果 nums[i] === nums[i-1]，说明这个数刚才已经作为“第一个数”处理过了，再处理一遍肯定会得到一样的结果。跳过！

2. 内层去重（针对 Left 和 Right）：

   当我们找到了一个合法的组合后，如果 nums[Left] === nums[Left+1]，说明下一个数还是一样，会导致结果重复。跳过！ 右边同理。

算法流程 (JavaScript)

1. 排序：nums.sort((a, b) => a - b)。

2. 外层循环：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，算两数之和。

• 难点：多了一层循环，也就多了一层剪枝和去重的逻辑。

准备好再加一层循环了吗？下期见！