#哈希表 #三数之和

3sum.cpp

class Solution {
public:

    inline void forward(vector<int>& nums, int k, int& j) {
        while (j < k && nums[j] == nums[j+1]) {
            j++;
        }
    }

    inline void backward(vector<int>& nums, int j, int& k) {
        while (j < k && nums[k] == nums[k-1]) {
            k--;
        }
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;

        for (int i = 0; i < nums.size() - 2; ++i) {
            if (nums[i] > 0)
                return ret;

            if (i > 0 && nums[i] == nums[i - 1])
                continue;
                        
            int j = i + 1;
            int k = nums.size() -1;
            while (j < k) {
                int value = nums[i] + nums[j] + nums[k];
                if (value < 0) {
                    forward(nums, k, j); // 滑过重复元素
                    j++;
                } else if (value > 0) {
                    backward(nums, j, k);
                    k--;
                } else if (value == 0) {
                    ret.push_back({nums[i], nums[j], nums[k]});
                    forward(nums, k, j);
                    backward(nums, j, k);
                    j++;
                    k--;
                }
            }
        }
        return ret;
    }
};