LeetCode Problem : 3Sum

Problem

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)

Code

vector<vector<int> > threeSum(vector<int> &num) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int n = num.size();

    vector<vector<int> > result;
    if(n < 3)
        return result;
    sort(num.begin(),num.end());
    int prev = INT_MIN;
    for(int i = 0;i < n - 2;++i){
        if(prev == num[i])
            continue;
        int target = -1*num[i];
        int l = i + 1;
        int r = n - 1;
        while(l < r){
            if(num[l] + num[r] < target)
                ++l;
                else if(num[l] + num[r] > target)
            --r;
            else{
                vector<int> tmp;
                tmp.push_back(min(num[l],num[i]));
                tmp.push_back(max(num[l],num[i]));
                tmp.push_back(num[r]);
                result.push_back(tmp);
                int k = l + 1;
                while(k < r && num[k] == num[l])
                    ++k;
                l = k;
                k = r - 1;
                while(k >=  l && num[k] == num[r])
                    --k;
                r = k;
            }   
        }
        prev = num[i];
    }
    return result;
}