LeetCode 第 15 题：三数之和-平芜编程栈

三数之和：从 “暴力狂” 到 “双指针大师” 的修炼之路 🚀

一、LeetCode 第 15 题：三数之和

先来看看LeetCode上给出的题目描述：

给你一个整数数组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]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入： nums = [0,1,1] 输出： [] 解释： 唯一可能的三元组和不为 0 。

示例 3：

输入： nums = [0,0,0] 输出： [[0,0,0]] 解释： 唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

是不是看起来有点绕？别急，咱们从简单的开始盘，一步步搞定这个 “磨人小妖精”～

二、回顾两数之和：小试牛刀的开胃菜 🍴

在啃 “三数之和” 这块硬骨头前，必须先回味一下前面学过的 —— 两数之和。

1、暴力拆解：简单但 “费时间” 的莽夫做法 🤯

两数之和要找两个数加起来等于目标值，暴力法的思路特直接：拿每个数跟它后面的数挨个配对，看和是不是目标值。

代码长这样：

javascript

function twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } return []; }

这方法时间复杂度是 O (n²)，就像在操场找两个人，挨个问 “你们俩加起来够不够 100 斤”，人多了真扛不住～

2、hashMap 求差：用空间换时间的 “小聪明” 💡

既然暴力法太费时间，咱换个思路：用哈希表存下每个数的位置，然后对每个数nums[i]，直接算target - nums[i]是不是在哈希表里。

代码示例：

javascript

function twoSum(nums, target) { const map = new Map(); for (let i = 0; i < nums.length; i++) { const complement = target - nums[i]; if (map.has(complement)) { return [map.get(complement), i]; } map.set(nums[i], i); } return []; }

这招时间复杂度降到 O (n)，空间复杂度 O (n)，相当于给每个人发个名牌，找的时候直接按名字喊，效率瞬间飙升！

想要具体学习两数之和问题的同学可以看看我前面的文章：https://blog.csdn.net/2302_80706750/article/details/155208999?spm=1001.2014.3001.5501。

三、三数之和：升级打怪的正餐时间 🍲

两数之和搞定了，三数之和怎么搞？别急，咱们先从 “莽夫” 开始，再进化成 “智者”。

1、暴力拆解：三重循环的 “时间杀手” ⏳

最直接的想法：三个数嘛，那就三重循环，挨个试！

代码大概长这样：

javascript

function threeSum(nums) { const res = []; const len = nums.length; // 先排序方便去重（虽然暴力法去重麻烦，但先排个序看着舒服） nums.sort((a, b) => a - b); for (let i = 0; i < len - 2; i++) { // 跳过重复的i（暴力法去重的雏形） if (i > 0 && nums[i] === nums[i - 1]) continue; for (let j = i + 1; j < len - 1; j++) { if (j > i + 1 && nums[j] === nums[j - 1]) continue; for (let k = j + 1; k < len; k++) { if (k > j + 1 && nums[k] === nums[k - 1]) continue; if (nums[i] + nums[j] + nums[k] === 0) { res.push([nums[i], nums[j], nums[k]]); } } } } return res; }

但这时间复杂度是 O (n³)，想象一下如果数组有 1000 个元素，那就是 10 亿次运算，电脑看了都得哭😭 显然这招在 LeetCode 上是会超时的，不能通过 LeetCode ，必须换思路！

2、双指针解法：排序 + 指针的 “黄金组合” 🌟

这才是解决三数之和的 “正道之光”！核心思路是：先排序，再固定一个数，剩下两个数用双指针找 —— 把三数问题降成两数问题，妙啊～

（1）第一步：排序！排序！排序！（重要的事说三遍）

为啥要排序？因为排序后：

方便跳过重复元素（重复的数挨在一起，一眼就能看出来）
能让双指针 “有规律地移动”（左边小右边大，和大了就左移右指针，和小了就右移左指针）

JavaScript 数组的sort()方法默认是按字符串排序的，所以必须传个比较函数：

javascript

// 升序排列（从小到大）：a - b < 0 时，a在前b在后（不交换） nums.sort((a, b) => a - b); // 降序排列（从大到小）：b - a < 0 时，b在前a在后（不交换） // nums.sort((a, b) => b - a);

比如[2,3,2,1,4,9]排序后就成了[1,2,2,3,4,9]，是不是清爽多了？

（2）第二步：固定一个数，派出 “左右护法” 指针

固定一个起点i（从 0 开始），然后左指针left从i+1出发，右指针right从数组末尾出发，三者形成 “铁三角”。

（3）第三步：根据三数之和 “指挥” 指针移动

计算sum = nums[i] + nums[left] + nums[right]：

如果sum === 0：完美！加入结果集，然后让left右移、right左移，继续找下一组
如果sum < 0：和太小了，让left右移找个大点的数
如果sum > 0：和太大了，让right左移找个小点的数

（4）第四步：跳过重复元素，拒绝 “复制粘贴”

这是关键！不然答案里会有重复的三元组：

对i：如果nums[i] === nums[i-1]，说明和上一个起点一样，直接跳过（注意i > 0才跳，第一个元素不能跳）
对left：找到一组解后，left右移时如果和前一个数一样，继续右移
对right：找到一组解后，right左移时如果和后一个数一样，继续左移

（5）完整代码：双指针的 “实战演练”

javascript

function threeSum(nums) { // 先排序，升序排列方便操作 nums.sort((a, b) => a - b); const res = []; // 固定i，注意i最多到length-3（因为要留left和right的位置） for (let i = 0; i < nums.length - 2; i++) { // 跳过重复的起点i if (i > 0 && nums[i] === nums[i - 1]) { continue; } // 左右指针：left是i的下一个，right是数组末尾 let left = i + 1; let right = nums.length - 1; // 指针没相遇就继续找 while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { // 找到一组解，加入结果 res.push([nums[i], nums[left], nums[right]]); // 移动指针继续找 left++; right--; // 跳过重复的left while (left < right && nums[left] === nums[left - 1]) { left++; } // 跳过重复的right while (left < right && nums[right] === nums[right + 1]) { right--; } } else if (sum < 0) { // 和太小，left右移找大点的数 left++; } else { // 和太大，right左移找小点的数 right--; } } } return res; }

这方法时间复杂度是 O (n²)（排序占 O (nlogn)，循环占 O (n²)），空间复杂度 O (1) 或 O (n)（取决于排序算法），比暴力法可优雅太多了～

四、面试官可能会抛来的 “灵魂拷问” 🧐

为啥三数之和要先排序？答：排序不仅能方便去重（重复元素挨在一起），还能让双指针有规律地移动（根据和的大小调整指针方向），这是双指针解法的核心前提～
时间复杂度怎么算的？答：排序是 O (nlogn)，外层循环 O (n)，内层双指针循环 O (n)，整体是 O (n²)，比暴力法的 O (n³) 好太多啦～
去重逻辑为什么要那么写？比如i > 0才跳？答：因为i=0是第一个元素，前面没元素可比，直接跳就错啦；而i>0时如果和前一个一样，说明重复了，必须跳，否则会出现重复的三元组～
两数之和能用双指针吗？三数之和为啥不用哈希表？答：两数之和用哈希表更简单（O (n)），双指针也能用但需要先排序（O (nlogn)）；三数之和用哈希表去重太麻烦，双指针配合排序去重更优雅，所以选双指针～