3Sum

[3Sum]

Given an array S of n integers, are there elements abc 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 O(n^2). 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s