# [leetcode] 3Sum

### 3Sum

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, abc)
• 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)
```

tags: array, two pointers

n^3复杂度，倒不是超时，而是输出超界(OUTPUT LIMIT EXCEEDED)。看来原数组中有很多重复数字，导致我产生了过多的重复解(duplicate)，尝试优化中。

```class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int>> re;
for(vector<int>::iterator it1 = num.begin(); it1 != num.end(); it1++){
for(vector<int>::iterator it2 = it1; it2 != num.end(); it2++){
for(vector<int>::iterator it3 = it2; it3 != num.end(); it3++){
if(*it1 + * it2 + *it3 == 0){
vector<int> thisRe;
thisRe.push_back(*it1);
thisRe.push_back(*it2);
thisRe.push_back(*it3);
sort(thisRe.begin(), thisRe.end());
re.push_back(thisRe);
}
}
}
}
return re;
}
};```

2.2更新

```class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int>> re;
unordered_map<int, int> m;
if(num.empty() == true || num.size() < 3){
return re;
}
sort(num.begin(), num.end());
for(vector<int>::iterator it = num.begin(); it != num.end(); it++){
if(m.find(*it) == m.end()){
m[*it] = 1;
}
else{
m[*it]++;
}
}
vector<int>::iterator it1 = num.begin();
while(it1!= num.end()){
vector<int>::iterator it2 = it1 + 1;
while(it2 != num.end()){
int a = *it1;
int b = *it2;
int target = 0 - a - b;
if(target < b){//repeated possible result
break;
}
else if(m.find(target) != m.end()){//found
int count = m[target];
if((a == b && a == target && count < 3) || ((target == b) && count < 2)){
//not enough num
;
}
else{
vector<int> thisRe;
thisRe.push_back(a);
thisRe.push_back(b);
thisRe.push_back(target);
re.push_back(thisRe);
}
}
it2++;
while(*it2 == *(it2-1) && it2 != num.end()){
it2++;
}
}
/*move it1 */
it1++;
while(*it1 == *(it1 - 1) && it1 != num.end()){
it1++;
}
}
return re;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.