#哈希表 #四数之和

4sum.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>> fourSum(vector<int>& nums, int target) {
        if (nums.size() < 4) return {};

        sort(nums.begin(), nums.end());
        if ((target > 0 && nums[0] > target) 
            || (target < 0 && nums.back() < target)) 
            return {};

        vector<vector<int>> ret;
        for (int a = 0; a < nums.size() - 3; ++a) {
            if ((target > 0 && nums[a] >= target) || (target == 0 && nums[a] > 0)
                || (target < 0 && nums[a] > 0))
                break;

            if (a > 0 && nums[a] == nums[a - 1])
                continue;

            // -3 1 1 1 2 5
            for (int b = a+1; b < nums.size() - 2; ++b) {
                if (b > a+1 && nums[b] == nums[b - 1])
                    continue;

                long ab = (long)nums[a] + nums[b]; // int 整型溢出
                if ((target > 0 && ab >= target) || (target == 0 && ab > 0)
                    || (target < 0 && ab > 0))
                    break;

                int c = b + 1;
                int d = nums.size() -1;
                while (c < d) {
                    long value = (long)nums[a] + nums[b] + nums[c] + nums[d]; // int 整型溢出
                    if (value < target) {
                        forward(nums, d, c); // 滑过重复元素
                        c++;
                    } else if (value > target) {
                        backward(nums, c, d);
                        d--;
                    } else if (value == target) {
                        ret.push_back({nums[a], nums[b], nums[c], nums[d]});
                        forward(nums, d, c);
                        backward(nums, c, d);
                        c++;
                        d--;
                    }
                }
            } // b
        } // a
        return ret;
    }
};