题解 | 三数之和

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > threeSum(vector<int>& num) {
        // write code here
        sort(num.begin(), num.end());
        int n = num.size();
        vector<vector<int>> result;
        for (int i = 0; i < n; ++i) {
            if (num[i] > 0) continue;
            if (i > 0 && num[i] == num[i - 1]) continue;

            int left = i + 1, right = n - 1;
            while (left < right) {
                if (num[i] + num[left] + num[right] == 0) {
                    result.emplace_back(vector<int> {num[i], num[left], num[right]});
                    while (left + 1 < right && num[left] == num[left + 1]) ++left;
                    while (left < right - 1 && num[right] == num[right - 1]) --right;
                    ++left;
                    --right;
                } else if (num[i] + num[left] + num[right] > 0) {
                    --right;
                } else {
                    ++left;
                }

            }
        }
        return result;
    }
};