跳转至

18 四数之和

把之前两数之和和三数之和的通用框架方法总结一下,我们会发现:

实际上通用框架的思路就是,假设要求n数之和,那么:

  1. 首先遍历第一个数nums[i],计算target - nums[i]
  2. 求n - 1数之和,其target(new)为target - nums[i], start为i + 1,得到结果集tuples
  3. 将tuples中的每个结果tuple都添加nums[i],放入新的结果集ans,最后返回即可
  4. 注意nums[i]的去重

这个思路体现了nSum递归的本质,为此我们可以将两数之和的代码和三数之和的代码结合在一起:

vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, int target){
    vector<vector<int>> ans;
    if(n <= 1)  
        return {};
    if(n == 2){
        int left = start, right = nums.size() - 1;
        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum < target){
                left++;
            }else if(sum > target){
                right--;
            }else if(sum == target){
                ans.push_back({nums[left], nums[right]});
                while(left < right && nums[left] == nums[left + 1]) left++;
                while(left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
        return ans;
    }else{
        // i需要从start开始
        for(int i = start; i < nums.size(); i++){
            vector<vector<int>> tuples = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for(vector<int>& tuple : tuples){
                tuple.push_back(nums[i]);
                ans.push_back(tuple);
            }
            while(i + 1 < nums.size() && nums[i] == nums[i + 1]) i++;
        }
        return ans;
    }
}

那么四数之和调用就是:

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

当然我们还可以进一步优化,最终优化为:

class Solution {
public:
    // target使用long防止数据溢出
    vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, long target){
        int sz = nums.size();
        vector<vector<int>> ans;
        // 对数组大小和n进行比较
        if(n <= 1 || sz < n)  
            return {};
        if(n == 2){
            int left = start, right = nums.size() - 1;
            while(left < right){
                // sum使用long防止数据溢出
                long sum = nums[left] + nums[right];
                if(sum < target){
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    left++;
                }else if(sum > target){
                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    right--;
                }else if(sum == target){
                    ans.push_back({nums[left], nums[right]});
                    while(left < right && nums[left] == nums[left + 1]) left++;
                    while(left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }else{
            for(int i = start; i < nums.size(); i++){
                vector<vector<int>> tuples = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for(vector<int>& tuple : tuples){
                    tuple.push_back(nums[i]);
                    ans.push_back(tuple);
                }
                while(i + 1 < nums.size() && nums[i] == nums[i + 1]) i++;
            }
        }
        return ans;
    }
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return nSumTarget(nums, 4, 0, target);
    }
};

当然这只是通用框架的写法,方便记忆,可以把过程都展开为迭代等等