Leetcode|15/18中3Sum/4Sum/nSum通用秒杀

vector<int> twoSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int size = nums.size();
    int left = 0, right = size - 1;
    while (left < right) {
        int diff = target - nums[right];
        if (diff == nums[left]) return {nums[left], nums[right]};
        if (diff > nums[left]) left++;
        else right--;
    }
    return {0, 0};
}

vector<vector<int>> twoSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int size = nums.size();
    int left = 0, right = size - 1;
    vector<vector<int>> res;
    while (left < right) {
        int diff = target - nums[right];
        if (diff > nums[left]) left++;
        else if (diff < nums[left]) right--;
        if (diff == nums[left]) {
            res.push_back({nums[left], nums[right]});
            int leftnum = nums[left], rightnum = nums[right];
            while (left < right && leftnum == nums[left]) left++;
            while (left < right && rightnum == nums[right]) right--;
            /** 切记对于有重复元素情况下不能使用类似left + 1 < right的判断
                比如[2,2]，则如下两个循环均会跳过，使得外层进入死循环
            while (left + 1 < right && nums[left] == nums[left + 1]) left++;
            while (left < right - 1 && nums[right] == nums[right - 1]) right--;
            **/
        }
    }
    return res;
}

class Solution {
public:
    vector<vector<int>> nSum(vector<int>& nums, int target, int left, int right, int n) {
        vector<vector<int>> res;
        if (n == 2) 
            while (left < right) {
                int diff = target - nums[right];
                if (diff > nums[left]) left++;
                else if (diff < nums[left]) right--;
                else if (nums[left] == diff) {
                    res.push_back({nums[left], nums[right]});
                    int leftnum = nums[left], rightnum = nums[right];
                    while (left < right && nums[left] == leftnum) left++;
                    while (left < right && nums[right] == rightnum) right--;
                }
            }
        else 
            for (int i = left; i <= right; i++) {
                auto sub = nSum(nums, target - nums[i], i + 1, right, n - 1);
                for (auto& tmp : sub) {
                    tmp.push_back(nums[i]);
                    res.push_back(tmp);
                }
                while (i < right && nums[i] == nums[i + 1]) i++;
            }
        return res;
    }

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return nSum(nums, target, 0, nums.size() - 1, 4);
    }
};