NSum之和

3Sum之和

15. 三数之和

思想：双指针

1. 将数组排序
2. 双指针分别指向i+1，nums.size()-1的位置
3. 求和，比较，移动双指针

要注意的是去重的逻辑

vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for(int i=0; i<n; i++){
            if(nums[i]>0) break;
            if(i>0 && nums[i]==nums[i-1]) continue;
            int l = i+1, r = n-1;
            while(l<r){
                if(nums[i]+nums[l]+nums[r]>0) r--;
                else if(nums[i]+nums[l]+nums[r]<0) l++;
                else{
                    ans.push_back({nums[i], nums[l], nums[r]});
                    while(l<r && nums[l]==nums[l+1]) l++;
                    while(l<r && nums[r]==nums[r-1]) r--;
                    // 两边指针同时收缩
                    l++;
                    r--;
                }
            }
        }
        return ans;
}

4Sum之和

18. 四数之和
与上一题类似，注意要进行两层剪枝，去重。

vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

        int n = nums.size();
        vector<vector<int>> ans;

        for(int i=0; i<n; i++){
            // 剪枝处理
            if(nums[i]>target && nums[i]>=0) break;
            // 对nums[i]去重
            if(i>0 && nums[i]==nums[i-1]) continue;

            for(int j=i+1; j<n; j++){
                // 二级剪枝处理
                if(nums[i]+nums[j]>target && nums[i]+nums[j]>=0) break;
                if(j>i+1 && nums[j]==nums[j-1]) continue;

                int l = j+1, r = n-1;
                while(l<r){
                    if((long) nums[i]+nums[j]+nums[l]+nums[r]>target) r--;
                    else if((long) nums[i]+nums[j]+nums[l]+nums[r]<target) l++;
                    else{
                        ans.push_back(vector<int>{nums[i], nums[j], nums[l], nums[r]});
                        while(l<r && nums[l]==nums[l+1]) l++;
                        while(l<r && nums[r]==nums[r-1]) r--;
                        l++;
                        r--;
                    }
                }
            }
        }
        return ans;
}