题目
给你一个包含 n 个整数的数组 nums ，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。（ 注意：答案中不可以包含重复的三元组。）
假设：
-
nums为[-1, 0, 1, 2, -1, -4] - 应返回
[ [-1, 0, 1], [-1, -1, 2] ]
算法优化解析
- 所有
求和的问题都可以转换为求差 - 像这题目普遍做法是三层循环嵌套，但这时间复杂度就是
O(n^3)，应该考虑用空间换时间，尽可能的少遍历。
像这倒题目：
- 采取固定最左边的第一个(
i)，剩下的两个使用双指针的方法，一左(j = i+ 1)和一右(k = nums.length - 1) - 如果
nums[i] + num[j] + nums[k] > 0，说明右边指针太大，应向左移(k--)，若左移后的值是重复值再向左移。 - 如果
nums[i] + num[j] + nums[k] < 0，说明左边指针大小，应向右移(j++)，若右移后的值是重复值再向右移。 - 如果
nums[i] + num[j] + nums[k] === 0，就是这三个，加到结果数组中。
完整代码
const threeSum = (nums) => {
// 先从小到大排序 nums
const data = nums.sort((a, b) => a - b)
// 结果数组
const res = []
// 缓存 nums 的长度
const len = nums.length
// 注意，遍历到倒数第三个就可以了，因为左右指针会遍历后面两个数
for (let i = 0; i < nums.length - 2; i++) {
// 左指针
let j = i + 1
// 右指针
let k = len - 1
// 如果遇到重复的数字，则跳过
if (i > 0 && nums[i] === nums[i-1]) {
continue
}
while (j < k) {
// 如果加起来大于 0 ，右指针往左移
if (data[i] + data[j] + data[k] > 0) {
k--
// 如果往左移后值还是相等，继续移动
while (data[k] === data[k + 1]) {
k--
}
} else if (data[i] + data[j] + data[k] < 0) {
// 如果加起来小于 0 ，左指针往右移
j++
// 如果往右移后值还是相等，继续移动
while (data[j] === data[j - 1]) {
j++
}
} else {
// 如果加起来等于 0，得到目标数字组合，推入结果数组
res.push([data[i], data[j], data[k]])
// 左右指针都往中间移动
j++
k--
// 有重复都跳过
while (data[j] === data[j - 1]) {
j++
}
while (data[k] === data[k + 1]) {
k--
}
}
}
}
return res
}
