3 Sum详解编程语言

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. 
 
Example 
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: 
 
(-1, 0, 1) 
(-1, -1, 2) 
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.

class Solution { 
public: 
    vector<vector<int> > threeSum(vector<int> &num)  
    { 
        vector<vector<int> > result; 
        if (num.size() < 3) return result; 
 
        int ans = 0; 
 
        sort(num.begin(), num.end()); 
 
        for (int i = 0;i < num.size() - 2; ++i) 
        { 
            if (i > 0 && num[i] == num[i - 1])   
                continue; 
            int j = i + 1; 
            int k = num.size() - 1; 
 
            while (j < k) 
            { 
                ans = num[i] + num[j] + num[k]; 
 
                if (ans == 0) 
                { 
                    result.push_back({num[i], num[j], num[k]}); 
                    ++j; 
                    while (j < num.size() && num[j] == num[j - 1]) 
                        ++j; 
                    --k; 
                    while (k >= 0 && num[k] == num[k + 1]) 
                        --k; 
                } 
                else if (ans > 0)  
                    --k; 
                else  
                    ++j; 
            } 
        } 
 
        return result; 
    } 
};