Description
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: The solution set must not contain duplicate triplets.
Example
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Discussion
这是一个求3个数的和为一个特定值的问题。首先我们对数组进行排序。
然后，固定第一个数firPos。然后用两个指针secPos和thiPos分别指向数组剩余数字的头和尾。然后往中间移动。
这个题目和Two Sum类似。
算法的时间复杂度为O(n^2)。
C++ Code
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> answer;
if(nums.size() < 3)
{
return answer;
}
sort(nums.begin(), nums.end());
for(int firPos = 0; firPos < nums.size() - 2; firPos++)
{
//若第一个数就大于0，明显不会再有答案
if(nums[firPos] > 0)
{
break;
}
//给第一个指针去重
if(firPos > 0 && nums[firPos] == nums[firPos - 1])
{
continue;
}
int secPos = firPos + 1;
int thiPos = nums.size() - 1;
while(secPos < thiPos)
{
int sum = nums[firPos] + nums[secPos] + nums[thiPos];
if(sum < 0)
{
secPos ++;
}
else if(sum > 0)
{
thiPos --;
}
else //sum == 0, add the set to answer
{
vector<int> temp(3, 0);
temp[0] = nums[firPos];
temp[1] = nums[secPos];
temp[2] = nums[thiPos];
answer.push_back(temp);
secPos ++;
thiPos --;
//cout << nums[firPos];
}
//给第二个指针去重
while(secPos < thiPos && secPos > firPos + 1&& nums[secPos] == nums[secPos - 1])
{
secPos ++;
}
//给第三个指针去重
while(secPos < thiPos && thiPos < nums.size() - 1 && nums[thiPos] == nums[thiPos + 1])
{
thiPos --;
}
}
}
return answer;
}
};