3Sum.txt

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > rets;
        if (num.size() < 3)
            return rets;
        sort(num.begin(), num.end());
        for (size_t i = 0; i < num.size() - 2; i++) {
            if ((i > 0) && (num[i] == num[i-1]))
                continue;
            size_t l = i + 1, u = num.size() - 1;
            while (l < u) {
                long long sum = (long long)num[i] + num[l] + num[u];
                if (sum == 0) {
                    rets.push_back(vector<int> (3, num[i]));
                    rets.back()[1] = num[l];
                    rets.back()[2] = num[u];
                }
                if (sum < 0)
                    while ((++l < u) && (num[l] == num[l-1]));
                else
                    while ((--u > l) && (num[u] == num[u+1]));
            }
        }
        return rets;
    }
};