0015.三数之和
难度：🟡 中等
标签：数组、双指针、排序
链接：15. 三数之和
题目描述
给你一个整数数组 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,0,0.md)
解释：唯一可能的三元组和为 0 。
解题思路
核心思想
本题的核心是找出所有和为 0 的、不重复的三元组。如果直接使用三层循环暴力求解，时间复杂度会达到 O(n³)，并且处理重复三元组会非常麻烦。为了优化，我们可以先对数组进行排序，然后利用数组的有序性来高效地查找。
思路选择
排序 + 双指针 是解决此问题的标准最优思路。
我们将原问题
a + b + c = 0转化为：固定一个数a，在数组的剩余部分寻找两个数b和c，使得b + c = -a。这本质上是一个“两数之和”的问题。通过先对数组排序，我们可以使用双指针法在线性时间内解决这个“两数之和”的子问题。
关键步骤
排序：首先对整个数组
nums进行升序排序。遍历与固定：用一个
for循环遍历数组，固定第一个数nums[i]。 a. 剪枝优化：如果nums[i] > 0，由于数组已排序，后面的数必然也大于 0，三数之和不可能为 0，可以直接结束循环。 b. 去重：如果nums[i]与前一个数nums[i-1]相同，为避免产生重复的三元组，应跳过当前循环。双指针查找： a. 初始化左指针
left = i + 1和右指针right = nums.length - 1。 b. 在left < right的条件下进行循环。 c. 计算三数之和sum = nums[i] + nums[left] + nums[right]。 d. 根据和调整指针： i. 如果sum < 0，说明和太小，需要增大，将左指针left右移。 ii. 如果sum > 0，说明和太大，需要减小，将右指针right左移。 iii. 如果sum === 0，说明找到了一个有效三元组。将其存入结果集。 e. 对left和right去重：在找到一个解后，为避免重复，需要将left和right指针移动到下一个不同的元素上。返回结果：遍历结束后，返回包含所有不重复三元组的结果集。
代码实现
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const results = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
// 剪枝：如果当前数字大于0，则三数之和一定大于0
if (nums[i] > 0) break;
// 去重：跳过相同的第一个数
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
results.push([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 results;
};
复杂度分析
时间复杂度：O(n²) 数组排序的时间复杂度为 O(n log n)。
for循环和while循环构成了 O(n²) 的复杂度。总体上，O(n²) 占主导地位。空间复杂度：O(log n) 或 O(n) 不考虑存储结果的数组，空间复杂度主要取决于排序算法所需的栈空间。
相关题目
总结
本题是“排序 + 双指针”模式的经典应用，是面试中考察数组操作、算法优化和细节处理能力的高频题。其核心在于通过排序将问题转化为更易于处理的“两数之和”，并通过双指针和去重逻辑高效地找出所有解。