Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
69 lines (56 sloc) 1.94 KB
/*
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]
]
*/
/*
Hints:
Three steps to optimize your algorithm:
1. Use 'std::sort' to sort the vector
2. We want to get 'a + b + c = 0', then we can fix the first number.
Use two pointer to find another two number.
The head pointer points to the one behind the first number.
The tail pointer points to the tail of the vector.
3. We need to get rid of duplicate answers.
If you use 'find(nums.begin(), nums.end(), answer)', it will 'Time Limit Exceeded'.
We need to change our mind: the vector after sorting has certain rules.
(1). if(sum == 0) while(l<r && nums[l] == answer[1]) ++l;
(2). if(sum == 0) while(l<r && nums[r] == answer[r]) --r;
(3). while(i<size-1 && nums[i]==nums[i+1]) ++i;
*/
class Solution {
protected:
vector<vector<int>> result;
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int size = nums.size();
if(!size) return result;
sort(nums.begin(), nums.end());
for(int i=0;i<size-2;i++){
int l = i+1, r = size-1, sum = 0;
while(l<r){
sum = nums[i] + nums[l] + nums[r];
if(sum == 0){
vector<int> tmp(3, 0);
tmp[0] = nums[i];
tmp[1] = nums[l];
tmp[2] = nums[r];
result.push_back(tmp);
while(l<r && nums[l] == tmp[1]) ++l;
while(l<r && nums[r] == tmp[2]) --r;
}
else if(sum > 0) --r;
else if(sum < 0) ++l;
}
while(i+1 < size && nums[i] == nums[i+1]) ++i;
}
return result;
}
};