18. 4Sum

左右夹逼O(n³) time O(1) space
kSum的复杂度下界是O(n^k-1)

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if not nums: return []
        nums.sort()
        n, res = len(nums), []
        # mx = nums[-1]
        for i in range(n):
            # if nums[i] + 3 * mx < target: continue
            # if 4 * nums[i] > target: break
            if i > 0 and nums[i - 1] == nums[i]: continue
            for j in range(i + 1, n):
                # if nums[i] + nums[j] + 2 * mx < target: continue
                # if nums[i] + 3 * nums[j] > target: break
                if j > i + 1 and nums[j - 1] == nums[j]: continue
                l, r, t = j + 1, n - 1, target - nums[i] - nums[j]
                while l < r:
                    s = nums[l] + nums[r]
                    if s == t:
                        res.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l - 1] == nums[l]: l += 1
                        r -= 1
                        while l < r and nums[r] == nums[r + 1]: r -= 1
                    elif s < t:
                        l += 1
                        while l < r and nums[l - 1] == nums[l]: l += 1
                    else:
                        r -= 1
                        while l < r and nums[r] == nums[r + 1]: r -= 1
        return res

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        if (n < 4) return {};
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 注意跳过重复的数
            for (int j = i + 1; j < n; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 注意跳过重复的数
                int l = j + 1, r = n - 1;
                int t = target - nums[i] - nums[j];
                while (l < r) {
                    int s = nums[l] + nums[r];
                    if (s < t) {
                        do { ++l; } while (l < r && nums[l] == nums[l - 1]);
                    } else if (s > t) {
                        do { --r; } while (l < r && nums[r] == nums[r + 1]);
                    } else {
                        res.push_back({nums[i], nums[j], nums[l], nums[r]});
                        do { ++l; } while (l < r && nums[l] == nums[l - 1]);
                        do { --r; } while (l < r && nums[r] == nums[r + 1]);
                    }
                }
            }
        }
        return res;
    }
};