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.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size();
vector<vector<int>> res;
for(int i=0;i<n-2;i++){
if(i>0 && (nums[i]==nums[i-1]) )continue;
int l=i+1, r= n-1;
while(l<r){
int sum =nums[i]+nums[l]+nums[r];
if(sum<0) l++;
else if(sum>0)r--;
else {
res.push_back(vector<int>{nums[i],nums[l],nums[r]});
while(l+1<r && nums[l]==nums[l+1])l++;
while(l<r-1 && nums[r]==nums[r-1]) r--;
l++; r--;
}
}
}
return res;
//time is out!(the following is mine)
// int length = nums.size();
// vector<vector<int>> ret;
// for(int i=0;i<length;i++){
// for(int j=i+1;j<length;j++){
// for(int k=j+1;k<length;k++){
// if(nums[i] + nums[j] + nums[k] == 0){
// ret.push_back({nums[i],nums[j],nums[k]});
// }
// }
// }
// }
// vector<int> index;
// length = ret.size();
// for(int i=0;i<length;i++){
// for(int j=i+1;j<length;j++){
// // cout << checkSame(ret[i],ret[j]) << endl;
// if(checkSame(ret[i],ret[j])){
// // // index.push_back(i);
// ret[j] = {-1,-1,-1};
// }
// }
// }
// // for(int i=0;i<index.size();i++){
// // ret[index[i]] = {-1,-1,-1};
// // }
// for(vector<vector<int>>::iterator it = ret.begin();it!=ret.end();){
// // cout << (*it)[0] << (*it)[1] <<(*it)[2] <<endl;
// if((*it)[0] == 0 && (*it)[1] == 0 && (*it)[2] == 0){
// it++;
// continue;
// }
// if((*it)[0] == (*it)[1] && (*it)[1] == (*it)[2]){
// it = ret.erase(it);
// }
// else{
// it++;
// }
// }
// // ret.erase({-1,-1,-1});
// return ret;
}
bool checkSame(vector<int>& a,vector<int>& b){
int al = a.size();
int bl = b.size();
if(al != bl){
return false;
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
// cout << "a: " << a[0] << a[1] << a[2] << endl;
// cout << "b: " << b[0] << b[1] << b[2] << endl;
for(int i=0;i<al;i++){
if(a[i] != b[i]){
return false;
}
}
return true;
}
// void sort(vector<int>& v){
// int len = v.size();
// for(int i=0;i<len;i++){
// for(int j=0;j<len-i-1;j++){
// if(v[j] > v[j+1]){
// int t = v[j];
// v[j] = v[j+1];
// v[j+1] = t;
// }
// }
// }
// }
};
