Type：medium
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
这道题差点儿把我做自闭。。。
题干大意是说，给定一个 vector<int>，在其中能否找到三个数值，使得它们相加等于0，并返回所有符合条件的三元数组。
解法思路如下：首先将 vector 进行从小到大 sort 排序，依次取值，并在其后的数组中对这个数的相反数做 2sum。
当遍历到第 i 位时，设 front 为i + 1，back为n - 1。当front < back时，比较 target（即-nums[i]）和 nums[front] + nums[back] 的大小。若大于 target，则back--；反之，front++。当nums[front] + nums[back] 大小正好等于 target 时，将 nums[i]、nums[front]、nums[back] 的值存入同一个 vector 数组（注意此题返回的类型是一个vector<vector<int>>）。由于有可能有多解，因此在 front < back 的情况下，将 front 向前加到第一个与原 front 对应的nums[front] 不同值处。back 同理。
在对第 i 位进行后续数值遍历后，首先要检查 nums[i+1] 的值是否不同于 nums[i]，若相同，要预先将 i++，再重新进入循环。
这道题的考点应该是双重vector，但同时要小心 i++ 的处理，容易出错，我因为这个一直报错，枯了。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
std::sort(nums.begin(), nums.end());
int n = nums.size();
for(int i=0; i<n-2 && nums[i]<=0; i++){
int target = -nums[i];
int front = i + 1;
int back = n - 1;
while(front < back){
if(nums[front] + nums[back] > target){
back--;
}else if(nums[front] + nums[back] < target){
front++;
}else{
vector<int> triplets(3, 0);
triplets[0] = nums[i];
triplets[1] = nums[front];
triplets[2] = nums[back];
ret.push_back(triplets);
while(front<back && nums[front] == triplets[1]) front++;
while(front<back && nums[back] == triplets[2]) back--;
}
}
while((i+1) < n && nums[i] == nums[i+1]) i++;
}
return ret;
}
};
