先排序,然后以第一个值为基准开始遍历,用双指针求第二个值和第三个值。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> > res;
        if (num.size() < 3) return res;
        for (int i = 0; i < num.size() - 2; ++i) {
            int j = i + 1;
            int k = num.size() - 1;
            int target = -num[i];
            while (j < k) {
                if (num[j] + num[k] > target) --k;
                else if (num[j] + num[k] < target) ++j;
                else {
                    vector<int> current = {num[i], num[j], num[k]};
                    res.push_back(current);
                    while (j + 1 < k && num[j+1] == num[j]) ++j;  // 防止重复
                    while (k - 1 > j && num[k-1] == num[k]) --k;  // 防止重复
                    ++j; --k;
                }
            }
            while (i + 1 < num.size() - 2 && num[i+1] == num[i]) ++i;   // 防止重复
        }
        return res;
    }
};