Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4},
A solution set is: (-1, 0, 1) (-1, -1, 2)
华丽的分割线，刷OJ真的是磨练一个人的事情。。。。。。。。。。。。。。
class Solution {
public:
vector<vector> threeSum(vector& nums) {
vector<vector>result;
if (nums.size() < 3)
return vector<vector>{};
sort(nums.begin(), nums.end());
//去重复
for (int i = 0; i < nums.size() - 2; i++)
{
if(i > 0 && nums[i] == nums[i-1])continue;//重复的元素不用计算
int target2 = 0 - nums[i];
twosum(i+1, target2, nums,result);
}
return result;
}
void twosum(int start, int target, vector& nums, vector<vector>&result)
{
int first = start;
int second = nums.size()-1;
while (first < second)
{
int k = nums[first] + nums[second];
if (k < target)
{
first++;
} else if (k > target)
{
second--;
}
else
{
result.push_back(vector{nums[start-1], nums[first], nums[second]});
//为了防止出现重复的二元组，使结果等于target
int tmp = first + 1;
while (tmp< second && nums[tmp] == nums[first])
{
tmp++;
}
first = tmp;
tmp = second - 1;
while (tmp > first && nums[tmp] == nums[second])
{
tmp--;
}
second = tmp;
}
}
}
};
