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]
]
- 題目大意
給定一組整數(shù)莉给，找到數(shù)組中所有相加等于0的3個數(shù)颗搂，結(jié)果中不能有相同的一組萨脑。
其實基本算法就是簡單的枚舉府怯，可以做少量的優(yōu)化鳞骤。
首先我們將數(shù)組從小到大排序配乓，從最小的開始掃描纠炮。 跳過與之前相同的數(shù)字（已經(jīng)掃描過了）惕澎，接下來今豆，再剩余的數(shù)字中找到另外兩個數(shù)使他們3個的和為0嫌拣。 這里，剩余的數(shù)字指的是當(dāng)前數(shù)字之后的數(shù)字呆躲，因為之前的數(shù)字所有可能已經(jīng)被找到了异逐。在找另外兩個數(shù)字的時候，用兩個指針插掂，一個指向剩余數(shù)字中最小的灰瞻，一個指向剩余數(shù)字中最大的。當(dāng)三個數(shù)的和超過0時辅甥，將指向最大的數(shù)字指針向前移動（使數(shù)字更性腿蟆），反之將小指針向后移動璃弄。注意跳過相同的數(shù)字要销！
/**
* @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--; // 如果兩數(shù)相加比剩余的值大，減小較大的值
else {
j++; // 否則增加較小的值
}
}
}
return result;
};
