三数之和
JavaScript实现LeetCode第15题. 三数之和
题目描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解题方法
使用排序 + 双指针方法解决;
- 首先进行数组排序，时间复杂度 O(nlogn)
- 对数组nums进行遍历，每遍历一个值利用其下标 i，形成一个固定值
nums[i] - 如果
nums[i]大于0， 则三数之和必然无法等于0，直接结束循环 - 如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
- 再使用前指针指向
start = i + 1处，后指针指向end = nums.length - 1，也就是结尾处 - 根据
sum = nums[i] + nums[start] + nums[end]结果，判断 sum 与 0 的大小关系，满足则添加进入结果，此时start++; end--如果sum < 0，则start++, 如果sum > 0, 则end-- - sum === 0 的时候还要考虑结果重复的情况
- nums[start] == nums[start+1] 则会导致结果重复，应该跳过，start++
- nums[end] == nums[end-1] 则会导致结果重复，应该跳过，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;
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-06-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录