russ15.三数之和
题目描述
注意
给你一个整数数组 nums ，判断是否存在三元组
[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0请你返回所有和为 0 且不重复的三元组。注意：答案中
不可以包含重复的三元组。
示例
输入：
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]注意，输出的顺序和三元组的顺序并不重要。
思路
首先对数组进行从小到大排序
遍历数组，如果当前元素大于 0 终止循环 因为数组是从小到大排序过的
if (i > 0 && nums[i] == nums[i - 1]) continue;这是为了去重，排序后可能会存在连续相等的元素定义两个指针 L 、 R 分别指向当前遍历元素的右一位和数组最后一位
满足
L < R的条件下- 如果
nums[i] + nums[L] + nums[R] === 0将[nums[i], nums[L], nums[R]]存入结果集ans中，同时对左右两边分别去重处理，然后分别把左指针右移一位、右指针左移一位 - 如果
nums[i] + nums[L] + nums[R] > 0将右指针左移一位 - 如果
nums[i] + nums[L] + nums[R] < 0将左指针右移一位
- 如果
最后返回结果集
代码
js
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
let ans = []; // 存放结果集
const len = nums.length;
if (!nums || len < 3) return [];
nums.sort((a, b) => a - b);
for (let i = 0; i < len; i++) {
if (nums[i] > 0) break; // 如果当前元素大于 0 终止循环求解【因为数组是从小到大排序过的】
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
let L = i + 1,
R = len - 1;
while (L < R) {
const sum = nums[i] + nums[L] + nums[R];
if (sum === 0) {
ans.push([nums[i], nums[L], nums[R]]);
while (L < R && nums[L + 1] === nums[L]) L++;
while (L < R && nums[R - 1] === nums[R]) R--;
L++;
R--;
} else if (sum > 0) {
R--;
} else {
L++;
}
}
}
return ans;
};