[leetcode][***] ThreeSum

 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)

Algorithm:
1. i is the first one, j is the second one, k is from last.
2. skip duplicated ones for i and k.
3. if num[i] > 0 or num[k] < 0, false.

My Code:

vector<vector<int> >threeSum(vector<int> &num) {
    sort(num.begin(), num.end());
    vector<int> ret;
    for (int i = 0; i < (int)num.size() && num[i] <= 0; ++ i) {
        if (i && num[i] == num[i - 1]) continue;
        int j = i + 1;
        for (int k = (int)num.size() - 1; k > j && num[k] >= 0; -- k) {
            if (k < (int)num.size() - 1 && num[k] == num[k + 1]) 
                continue;
            while (j < k && num[i] + num[j] + num[k] < 0) ++ j;
            if (j < k && num[i] + num[j] + num[k] == 0) {
                int a[] = {num[i], num[j], num[k]};
                ret.push_back(vector<int>(a, a + 3));
            }
        }
    }
    return ret;
}