### [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,*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)

### [Analysis]

The most naive approach would be . Note that the sum is 0, if we sort the array at the beginning, we can save a lot of useless check.

There are several optimizations to make though, more details commented in the code.

vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > res; if (num.size() < 3) return res; sort(num.begin(), num.end()); for (int i=0; i<num.size()-2; ++i) { // there is no need to go further if num[i] doesn't change. // Suppose that we've found a new valid triplet, // it must be a duplicate because previous start and end are already included with this num[i] // Also, this gurantee that if num[i] has increased, // this won't be a duplicate, since we know that num[start] and num[end] are both greater than num[i] if (i>0 && num[i] == num[i-1]) continue; // we know that num[i] <= num[start] <= num[end], // if num[i] > 0 than there is no hope to find a valid triplet. if (num[i] > 0) break; int start = i+1, end = num.size()-1; while (start < end) { int s = num[start]+num[end]+num[i]; if(start>i+1 && num[start] == num[start-1]) { start++; continue; // Skip the same num[j] here. } if (s > 0) { end--; } else if (s < 0){ start++; } else { // something new since num[i] has increased vector<int> r = {num[i], num[start], num[end]}; res.push_back(r); start++; end--; } } } return res; }

Advertisements