15. 三数之和
给你一个整数数组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
解题思路：
（1）最直接的方法就是三个循环，从nums中取三个的全组合。之后在去除收集数据中的重复项，时间复杂度是大于的，这种方法会超时；
（2）第一层优化的想法是：对于重复，可以把整个数组排序，三重循环每次进行的时候判断本次的数是否和上次相同，如此取得的数据满足（a1,a2,a3）,一次递增或递减，每次取出来的数据一定是不重复的。
nums[ncount]//nums是有序数组
p1=0;
while (p1<ncount-2){
if (p1==0 || nums[p1]!=nums[p1-1]){
p2=p1+1;
while (p2<ncount-1){
if (p2==p1+1 || nums[p2]!=nums[p2-1]){
p3=p2+1;
while (p3<ncount){
if (p3==p2+1 || nums[p3]!=nums[p3-1]){
...
}
++p3;
}
}
++p2;
}
}
++p1;
}
（3）不过这个样子时间复杂度等于，还是会超时。
（4）注意到，当前两层循环的数字确定是，第三重循环里面如果存在则存在唯一一个值满足题意。并且当第二重循环数增大时，第三重循环值一定会比上一次减小，于是可以把后面两重循环的时间复杂度压缩一个等级，通常符合这种情况的数据都适用于双指针。
双指针：有序数组中选取两个数，如果当一个数增大时另一个数减小，就可以将
的时间复杂度变为
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
int ncount=nums.size();
int p1=0;
while (p1<ncount-2){
if (p1==0 || nums[p1]!=nums[p1-1]){
int p2=p1+1;
int p3=ncount-1;
while (p2<ncount-1 && p2!=p3){
if (p2==p1+1 || nums[p2]!=nums[p2-1]){
while (p3>p2 && nums[p1]+nums[p2]+nums[p3]>0) {--p3;}
if (!(p3>p2)) break;
if (nums[p1]+nums[p2]+nums[p3]==0){
vector<int> test={nums[p1],nums[p2],nums[p3]};
res.push_back(test);
}
}
++p2;
}
}
++p1;
}
return res;
}
