Monday, April 28, 2014

3 Sum -- Leetcode

Question:
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)

Answer:
Similar to "2 Sum", sort the array firstly, a + b + c = t, choose (a) from array every time, then find from the left right elements for b and c whose sum to be (t-a), using two pointer method here.
Note: there exists duplicate elements in the array, so we need to avoid duplicate triplets in the solution result!

vector<vector<int> > threeSum(vector<int> &num) {
    sort(num.begin(), num.end());
 
    vector<vector<int> > triplets;
    vector<int> triplet(3,INT_MIN);
 
    for (int i = 0;i < num.size(); i++) {
        if(i>0 && num[i]==num[i-1]) continue;     // To avoid duplicate triplets!
     
        int j = i + 1;
        int k = num.size() - 1;
        while (j < k) {
            if (num[i] + num[j] + num[k] < 0) {
                j++;
            } else if (num[i] + num[j] + num[k] > 0) {
                k--;
            } else {
                if(num[j]!=triplet[1] || num[k]!=triplet[2]){       // To avoid duplicate triplets!
                    triplet[0] = num[i];
                    triplet[1] = num[j];
                    triplet[2] = num[k];
                    triplets.push_back(triplet);
                }
                j++;
                k--;
            }
        }
    }
    return triplets;
}

No comments:

Post a Comment