题目描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解法
解法一（暴力掉头发法）
思路：
- 对数组进行三层遍历，通过三个游标，找到所有满足
a + b +c = 0的结果。 - 然后对结果进行去重，剔除重复的三元组。
缺点：
- 在leetcode执行，由于执行时间过长而失败。
var threeSum = function(nums) {
const result = [];
for (let i = 0; i < nums.length; i++) {
const a = nums[i];
for (let j = i + 1; j < nums.length - 1; j++) {
const b = nums[j];
for (let z = j + 1; z < nums.length; z++) {
const c = nums[z];
if (a + b + c === 0) {
result.push([a, b, c].sort((a,b) => a-b));
}
}
}
}
if (result.length === 0) return [];
const copy_result = result.slice(0);
for (let t = 0; t < result.length; t++) {
const temp_a = result[t];
for (let tx = t + 1; tx < result.length; tx++) {
const temp_b = result[tx];
if (temp_b.every((value, index) => value === temp_a[index])) {
delete copy_result[tx];
}
}
}
return copy_result.filter((value) => value != null);
};
解法二（推荐）
思路：
- 将数组排序
- 定义3个指针 i, j, k，遍历元素i，找到使
nums[j] + nums[k] = -nums[i]等式成立的结果集。这样，就能将三数之和的问题转化为两数之和的问题。
详细思路可以看老表同学的笔记，其中最有趣的是第二步的搜索过程，用到了双指针夹逼搜索，并且做了相同元素过滤处理：
老表同学的笔记
var threeSum = function(nums) {
const result = [];
nums.sort((a,b) => a - b);
for (let i = 0; i < nums.length; i++) {
if (i==0 || nums[i] > nums[i -1]) {
let j = i +1;
let k = nums.length - 1;
while (j < k) {
const sum = nums[i] + nums[j] + nums[k];
if (sum === 0) {
result.push([ nums[i], nums[j], nums[k] ]);
j++;
k--;
// 剔除相同参数
while (j<k && nums[j] === nums[j - 1]) {
j++;
}
// 剔除相同参数
while (k > j && nums[k] === nums[k+1]) {
k--;
}
} else if (sum > 0) {
k--;
} else if (sum < 0) {
j++;
}
}
}
}
return result;
};
时间复杂度：小于 O(n^2)
与方法一相比，执行速度非常快，而且效率高。
方法二执行结果
