JavaScript三数之和
2019-11-13 本文已影响0人
海蒂Hedy
<!-- 这题我们采用排序+双指针的思路来做,遍历排序后的数组,定义指针l和r,
分别从当前遍历元素的下一个元素和数组的最后一个元素往中间靠拢,
计算结果跟目标对比。 -->
<script>
var threeSum = function (nums) {
if (nums.length < 3) {
return [];
}
let res = [];
// 排序
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
// 去重
continue;
}
if (nums[i] > 0) {
// 若当前元素大于0,则三元素相加之后必定大于0
break;
}
// l为左下标,r为右下标
let l = i + 1; r = nums.length - 1;
while (l < r) {
let sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
res.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] == nums[l + 1]) {
l++
}
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
l++;
r--;
}
else if (sum < 0) {
l++;
}
else if (sum > 0) {
r--;
}
}
}
return res;
};
var nums2 = [-1, 0, 1, 2, -1, -4];
console.log(threeSum(nums2))
</script>