LeetCode 「中等」15.三数之和
题目描述
给你一个整数数组 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,1,1]
输出：[]
输入：nums = [0,0,0]
输出：[[0,0,0]]
解答
排序 + 双指针
Code
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
if (nums.length < 3) return [];
const ans = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 2; ++i) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // 跳过重复的固定元素
let lk = i + 1, rk = nums.length - 1;
while (lk < rk) {
const sum = nums[i] + nums[lk] + nums[rk];
if (sum === 0) {
ans.push([nums[i], nums[lk], nums[rk]]);
while (lk < rk && nums[lk] === nums[lk + 1]) ++lk; // 跳过重复的左指针元素
while (lk < rk && nums[rk] === nums[rk - 1]) --rk; // 跳过重复的右指针元素
++lk;
--rk;
} else if (sum > 0) {
--rk;
} else {
++lk;
}
}
}
return ans;
}