15. 三数之和
难度中等
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]
提示：
0 <= nums.length <= 3000-105 <= nums[i] <= 105
第一直觉就是暴力，数据量太大，无法暴力。
那么就对三重循环进行优化，考虑两数之和,a+b+c = 0, 则有 b+c = -a.
如果是升序数组，可以考虑用双指针来优化里面的两层循环。
-10, -1,0,1,2,2,3,4,7,9
first:0~n-1
second: first+1~n-1
third: n-1~second+1
nums[second] + nums[n-1] 大于 target才有继续走下去的意义（若小于了，那么以后就再也不可能会有等于的情况了，因为是升序数组嘛）， 此时third = n-1.
third不断自减，直到和second相遇，在这个过程中，要判断nums[second]+nums[third]是否等于target。若等于，则找到了答案，返回即可。
至此，还没解决一个重要的问题,就是去重。
由于数组nums中可能含有重复元素， 那么
对于 -1，-1，-1, 2，2
就会有三个结果[-1, -1, 2]、[-1, -1, 2]、[-1, -1, 2]
关键就是：对于每个位置，选过的数不能再选。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int> > ans; int n = nums.size(); if(n < 3) return {}; int target; sort(nums.begin(), nums.end()); for(int first=0; first<n; first++){ if(first>0 && nums[first] == nums[first-1]) continue;//选过的数不能再选 target = -nums[first]; int third = n-1; for(int second = first+1; second<n; second++){ if(second>first+1 && nums[second] == nums[second-1]) continue;//选过的数不能再选 while(second < third && nums[second]+nums[third] > target){ third--; } if(second == third) break;//此情况下，不可能找到满足条件的三元组了。 if(nums[second] + nums[third] == target) ans.push_back({nums[first], nums[second], nums[third]}); } } return ans; } };
时间复杂度：O(N^2) 其中 N 是数组 nums 的长度。
空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为O(logN)。然而我们修改了输入的数组nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了nums 的副本并进行排序，空间复杂度为 O(N)