Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
- 题目大意
给定一组整数，找到数组中所有相加等于0的3个数，结果中不能有相同的一组。
其实基本算法就是简单的枚举，可以做少量的优化。
首先我们将数组从小到大排序，从最小的开始扫描。 跳过与之前相同的数字（已经扫描过了），接下来，再剩余的数字中找到另外两个数使他们3个的和为0。 这里，剩余的数字指的是当前数字之后的数字，因为之前的数字所有可能已经被找到了。在找另外两个数字的时候，用两个指针，一个指向剩余数字中最小的，一个指向剩余数字中最大的。当三个数的和超过0时，将指向最大的数字指针向前移动（使数字更小），反之将小指针向后移动。注意跳过相同的数字！
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
nums.sort((a, b) => a - b);
const result = [];
console.log(nums);
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] === nums[i - 1]) { // 跳过相同的值
continue;
}
let j = i + 1;
let k = nums.length - 1;
const rest = -nums[i];
while (j < k) {
if (nums[j] + nums[k] === rest) {
result.push([nums[i], nums[j], nums[k]]);
while (j < k && nums[j] === nums[j + 1]) j++; // 跳过相同的值
while (j < k && nums[k] === nums[k - 1]) k--;
j++;
k--;
} else if (nums[j] + nums[k] > rest) k--; // 如果两数相加比剩余的值大，减小较大的值
else {
j++; // 否则增加较小的值
}
}
}
return result;
};
