题目
给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]输出：[]解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]输出：[[0,0,0]]解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
可以这样理解：三数之和 = 排序后，固定一个数，再用双指针找另外两个数。
为什么不能直接三重循环？
最容易想到的是：
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] + nums[j] + nums[k] == 0) { // 记录答案 } } } }问题有两个：
第一，时间复杂度是：
O(n^3)题目中：
nums.length <= 30003000^3太大，会超时。
第二，结果会重复。
例如：
nums = [-1, 0, 1, 2, -1, -4]里面有两个-1，所以可能多次得到：
[-1, 0, 1]但题目要求答案中不能有重复三元组。
为什么要排序？
排序后的数组有两个好处。
原数组：
[-1, 0, 1, 2, -1, -4]排序后：
[-4, -1, -1, 0, 1, 2]好处一：方便去重。
比如两个-1是挨在一起的：
[-4, -1, -1, 0, 1, 2] ↑ ↑所以我们可以判断：
if (i > 0 && nums[i] == nums[i - 1]) continue;意思是：
如果当前这个数和前一个数一样，说明之前已经以这个数作为第一个数找过答案了，这次直接跳过。好处二：可以使用双指针。
因为排序后，数组是有序的：
小 ---------------------- 大当三数之和太小时，可以让左指针右移，让总和变大。
当三数之和太大时，可以让右指针左移，让总和变小。
核心思路：固定一个数，寻找另外两个数
假设排序后：
[-4, -1, -1, 0, 1, 2]我们固定第一个数a。
比如：
a = -1那么问题就变成：
找两个数 b 和 c，使得： a + b + c = 0也就是：
b + c = -a如果：
a = -1那么：
b + c = 1这就变成了一个“两数之和”问题。
区别是：这里数组已经排序，所以可以用双指针，不需要哈希表。
4. 双指针怎么移动？
固定i作为第一个数：
int left = i + 1; int right = n - 1;然后计算：
sum = nums[i] + nums[left] + nums[right];分三种情况：
情况 1：sum == 0
说明找到一个答案：
ans.push_back({nums[i], nums[left], nums[right]});然后：
left++; right--;继续找下一个答案。
情况 2：sum < 0
说明当前和太小了。
因为数组已经排序，想让和变大，就要让left右移：
left++;例如：
[-4, -1, -1, 0, 1, 2] i L R sum = -4 + (-1) + 2 = -3太小了，所以left往右走，找更大的数。
情况 3：sum > 0
说明当前和太大了。
想让和变小，就要让right左移：
right--;例如：
[-4, -1, -1, 0, 1, 2] i L R sum = -1 + 0 + 2 = 1太大了，所以right往左走，找更小的数。
用示例完整走一遍
输入：
[-1, 0, 1, 2, -1, -4]排序：
[-4, -1, -1, 0, 1, 2]第一轮：固定 nums[i] = -4
i = 0 nums[i] = -4 left = 1 right = 5[-4, -1, -1, 0, 1, 2] i L R计算：
sum = -4 + (-1) + 2 = -3太小，left++。
继续：
[-4, -1, -1, 0, 1, 2] i L Rsum = -4 + (-1) + 2 = -3还是太小，left++。
继续：
[-4, -1, -1, 0, 1, 2] i L Rsum = -4 + 0 + 2 = -2还是太小，left++。
继续：
[-4, -1, -1, 0, 1, 2] i L Rsum = -4 + 1 + 2 = -1还是太小，left++。
此时left == right，结束。
这一轮没有答案。
第二轮：固定 nums[i] = -1
[-4, -1, -1, 0, 1, 2] i L R计算：
sum = -1 + (-1) + 2 = 0找到答案：
[-1, -1, 2]然后
left++ right--变成：
[-4, -1, -1, 0, 1, 2] i L R计算：
sum = -1 + 0 + 1 = 0找到答案：
[-1, 0, 1]继续移动：
left++ right--此时left >= right，结束。
第三轮：固定 nums[i] = -1
下标变成i = 2，但是
nums[2] == nums[1]也就是当前的-1和上一个-1重复。
所以跳过。
因为上一轮已经以-1作为第一个数找过答案了。
最终答案：
[[-1, -1, 2], [-1, 0, 1]]完整代码
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) { std::vector<std::vector<int>> result = {}; // 先对数组进行排序 std::sort(nums.begin(),nums.end()); int L = 1; int R = nums.size() - 1; for (int i = 0; i < nums.size();i++){ if(nums[i] > 0){ break; } if (i > 0 && nums[i] == nums[i-1]) // 跳过重复的第一个数 { continue; } L = i + 1; R = nums.size() - 1; // 在这里赋值是为了防止 nums[i] 和 nums[i-1] 相等时，L 和 R 没有被重置 while (L<R) { int sum = 0; sum = nums[i] + nums[L] + nums[R]; if(sum == 0){ result.push_back({nums[i],nums[L],nums[R]}); // 跳过重复的第二个数 while (L < R && nums[L] == nums[L + 1]) { L++; } // 跳过重复的第三个数 while (L < R && nums[R] == nums[R - 1]) { R--; } // 或者两个while循环合并 // while (L < R && nums[L] == nums[L + 1] && nums[R] == nums[R - 1]) { // L++; R--; // } 会增加常数级别的计算，性能会稍微下降 L++; R--; } else if (sum < 0){ L++; } else{ R--; } } // L=i+2; // R=nums.size() - 1; } return result; }这里精髓在于三次去重
第一次去重
if (i > 0 && nums[i] == nums[i - 1]) { continue; }这次去重还是很好理解的。如果 定 后一个数和前一个数一样，则必定是重复的。
第二次去重
这段代码：
while (L < R && nums[L] == nums[L + 1]) { L++; }意思是：
当前
nums[L]已经参与组成过一个答案了，如果右边还有相同的nums[L]，继续用它一定会产生重复三元组，所以直接跳过。
例如：
[-2, 0, 0, 0, 2] L当前L指向第一个0。
如果已经用：
[-2, 0, 2]作为答案，那么后面的0再和-2、2组合，还是：
[-2, 0, 2]所以要跳过所有重复的0。
第三次去重：跳过重复的 R
这段代码：
while (L < R && nums[R] == nums[R - 1]) { R--; }意思是：
当前
nums[R]已经参与组成过一个答案了，如果左边还有相同的nums[R]，继续用它一定会产生重复三元组，所以直接跳过。
例如：
[-2, 0, 2, 2, 2] R当前R指向最后一个2。
已经得到：
[-2, 0, 2]那么前面的那些2再参与组合，也还是：
[-2, 0, 2]所以要跳过所有重复的2。
