给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
使用排序 + 双指针
方法解决;
nums[i]
nums[i]
大于0, 则三数之和必然无法等于0,直接结束循环start = i + 1
处,后指针指向end = nums.length - 1
,也就是结尾处sum = nums[i] + nums[start] + nums[end]
结果,判断 sum 与 0 的大小关系,满足则添加进入结果,此时 start++; end--
如果 sum < 0
,则start++
, 如果 sum > 0
, 则 end--
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
let result = [];
let len = nums.length;
if(nums === null || len < 3) {
return result;
}
nums.sort((a, b) => a - b);
for(let i = 0; i < len; i++) {
// 如果当前数字大于0,则三数之和一定大于0,所以结束循环
if(nums[i] > 0) {
break;
}
// 去重
if( i > 0 && nums[i] === nums[ i - 1]) {
continue;
}
let start = i + 1;
let end = len - 1;
while(start < end) {
let sum = nums[i] + nums[start] + nums[end];
if(sum === 0) {
result.push([nums[i], nums[start], nums[end]]);
// 去重
while(start < end && nums[start] === nums[start + 1]) {
start++;
}
// 去重
while(start < end && nums[end] === nums[end - 1]) {
end--;
}
start++;
end--;
} else if(sum < 0) {
start++;
} else if(sum > 0) {
end--;
}
}
}
return result;
};