关于算法:一个方法团灭-nSum-问题

4次阅读

共计 6249 个字符，预计需要花费 16 分钟才能阅读完成。

常常刷 LeetCode 的读者必定晓得鼎鼎有名的 twoSum 问题，咱们上篇文章 twoSum 问题的核心思想就对 twoSum 的几个变种做了解析。

然而除了 twoSum 问题，LeetCode 下面还有 3Sum，4Sum 问题，我预计当前出个 5Sum，6Sum 也不是不可能。

那么，对于这种问题有没有什么好方法用套路解决呢？本文就由浅入深，层层推动，用一个函数来解决所有 nSum 类型的问题。

上篇文章写了力扣上的 twoSum 问题，题目要求返回的是索引，这里我来编一道 twoSum 题目：

如果假如输出一个数组 nums 和一个指标和 target， 请你返回 nums 中可能凑出 target 的两个元素的值 ，比方输出 nums = [1,3,5,6], target = 9，那么算法返回两个元素 [3,6]。能够假如只有且仅有一对儿元素能够凑出 target。

咱们能够先对 nums 排序，而后利用前文双指针技巧写过的左右双指针技巧，从两端相向而行就行了：

vector<int> twoSum(vector<int>& nums, int target) {
    // 先对数组排序
    sort(nums.begin(), nums.end());
    // 左右指针
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {int sum = nums[lo] + nums[hi];
        // 依据 sum 和 target 的比拟，挪动左右指针
        if (sum < target) {lo++;} else if (sum > target) {hi--;} else if (sum == target) {return {nums[lo], nums[hi]};
        }
    }
    return {};}

这样就能够解决这个问题，不过咱们要持续魔改题目，把这个题目变得更泛化，更艰难一点：

nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能呈现反复 。

函数签名如下：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target);

比如说输出为 nums = [1,3,1,2,2,3], target = 4，那么算法返回的后果就是：[[1,3],[2,2]]。

对于批改后的问题，要害难点是当初可能有多个和为 target 的数对儿，还不能反复，比方上述例子中 [1,3] 和 [3,1] 就算反复，只能算一次。

首先，基本思路必定还是排序加双指针：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target {
    // 先对数组排序
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {int sum = nums[lo] + nums[hi];
        // 依据 sum 和 target 的比拟，挪动左右指针
        if      (sum < target) lo++;
        else if (sum > target) hi--;
        else {res.push_back({lo, hi});
            lo++; hi--;
        }
    }
    return res;
}

然而，这样实现会造成反复的后果，比如说 nums = [1,1,1,2,2,3,3], target = 4，失去的后果中 [1,3] 必定会反复。

出问题的中央在于 sum == target 条件的 if 分支，当给 res 退出一次后果后，lo 和 hi 不应该扭转 1 的同时，还应该跳过所有反复的元素：

所以，能够对双指针的 while 循环做出如下批改：

while (lo < hi) {int sum = nums[lo] + nums[hi];
    // 记录索引 lo 和 hi 最后对应的值
    int left = nums[lo], right = nums[hi];
    if (sum < target)      lo++;
    else if (sum > target) hi--;
    else {res.push_back({left, right});
        // 跳过所有反复的元素
        while (lo < hi && nums[lo] == left) lo++;
        while (lo < hi && nums[hi] == right) hi--;
    }
}

这样就能够保障一个答案只被增加一次，反复的后果都会被跳过，能够失去正确的答案。不过，受这个思路的启发，其实前两个 if 分支也是能够做一点效率优化，跳过雷同的元素：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    // nums 数组必须有序
    sort(nums.begin(), nums.end());
    int lo = 0, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {int sum = nums[lo] + nums[hi];
        int left = nums[lo], right = nums[hi];
        if (sum < target) {while (lo < hi && nums[lo] == left) lo++;
        } else if (sum > target) {while (lo < hi && nums[hi] == right) hi--;
        } else {res.push_back({left, right});
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return res;
}

这样，一个通用化的 twoSum 函数就写进去了，请确保你了解了该算法的逻辑，咱们前面解决 3Sum 和 4Sum 的时候会复用这个函数。

这个函数的工夫复杂度非常容易看进去，双指针操作的局部尽管有那么多 while 循环，然而工夫复杂度还是 O(N)，而排序的工夫复杂度是 O(NlogN)，所以这个函数的工夫复杂度是 O(NlogN)。

这是力扣第 15 题「三数之和」：

题目就是让咱们找 nums 中和为 0 的三个元素，返回所有可能的三元组（triple），函数签名如下：

vector<vector<int>> threeSum(vector<int>& nums);

这样，咱们再泛化一下题目，不要光和为 0 的三元组了，计算和为 target 的三元组吧，同下面的 twoSum 一样，也不容许反复的后果：

vector<vector<int>> threeSum(vector<int>& nums) {
    // 求和为 0 的三元组
    return threeSumTarget(nums, 0);
}

vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {// 输出数组 nums，返回所有和为 target 的三元组}

这个问题怎么解决呢？ 很简略，穷举呗 。当初咱们想找和为 target 的三个数字，那么对于第一个数字，可能是什么？nums 中的每一个元素 nums[i] 都有可能！

那么，确定了第一个数字之后，剩下的两个数字能够是什么呢？其实就是和为 target - nums[i] 的两个数字呗，那不就是 twoSum 函数解决的问题么????

能够间接写代码了，须要把 twoSum 函数稍作批改即可复用：

/* 从 nums[start] 开始，计算有序数组
 * nums 中所有和为 target 的二元组 */
vector<vector<int>> twoSumTarget(vector<int>& nums, int start, int target) {
    // 左指针改为从 start 开始，其余不变
    int lo = start, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {...}
    return res;
}

/* 计算数组 nums 中所有和为 target 的三元组 */
vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
    // 数组得排个序
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    // 穷举 threeSum 的第一个数
    for (int i = 0; i < n; i++) {// 对 target - nums[i] 计算 twoSum
        vector<vector<int>> 
            tuples = twoSumTarget(nums, i + 1, target - nums[i]);
        // 如果存在满足条件的二元组，再加上 nums[i] 就是后果三元组
        for (vector<int>& tuple : tuples) {tuple.push_back(nums[i]);
            res.push_back(tuple);
        }
        // 跳过第一个数字反复的状况，否则会呈现反复后果
        while (i < n - 1 && nums[i] == nums[i + 1]) i++;
    }
    return res;
}

须要留神的是，相似 twoSum，3Sum 的后果也可能反复，比方输出是 nums = [1,1,1,2,3], target = 6，后果就会反复。

关键点在于，不能让第一个数反复，至于前面的两个数，咱们复用的 twoSum 函数会保障它们不反复 。所以代码中必须用一个 while 循环来保障 3Sum 中第一个元素不反复。

至此，3Sum 问题就解决了，工夫复杂度不难算，排序的复杂度为 O(NlogN)，twoSumTarget 函数中的双指针操作为 O(N)，threeSumTarget 函数在 for 循环中调用 twoSumTarget 所以总的工夫复杂度就是 O(NlogN + N^2) = O(N^2)。

这是力扣第 18 题「四数之和」：

函数签名如下：

vector<vector<int>> fourSum(vector<int>& nums, int target);

都到这份上了，4Sum 齐全就能够用雷同的思路：穷举第一个数字，而后调用 3Sum 函数计算剩下三个数，最初组合出和为 target 的四元组。

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    // 数组须要排序
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    // 穷举 fourSum 的第一个数
    for (int i = 0; i < n; i++) {// 对 target - nums[i] 计算 threeSum
        vector<vector<int>> 
            triples = threeSumTarget(nums, i + 1, target - nums[i]);
        // 如果存在满足条件的三元组，再加上 nums[i] 就是后果四元组
        for (vector<int>& triple : triples) {triple.push_back(nums[i]);
            res.push_back(triple);
        }
        // fourSum 的第一个数不能反复
        while (i < n - 1 && nums[i] == nums[i + 1]) i++;
    }
    return res;
}

/* 从 nums[start] 开始，计算有序数组
 * nums 中所有和为 target 的三元组 */
vector<vector<int>> 
    threeSumTarget(vector<int>& nums, int start, int target) {int n = nums.size();
        vector<vector<int>> res;
        // i 从 start 开始穷举，其余都不变
        for (int i = start; i < n; i++) {...}
        return res;

这样，依照雷同的套路，4Sum 问题就解决了，工夫复杂度的剖析和之前相似，for 循环中调用了 threeSumTarget 函数，所以总的工夫复杂度就是 O(N^3)。

在 LeetCode 上，4Sum 就到头了， 然而回忆方才写 3Sum 和 4Sum 的过程，实际上是遵循雷同的模式的 。我置信你只有略微批改一下 4Sum 的函数就能够复用并解决 5Sum 问题，而后解决 6Sum 问题……

那么，如果我让你求 100Sum 问题，怎么办呢？其实咱们能够察看下面这些解法，对立出一个 nSum 函数：

/* 留神：调用这个函数之前肯定要先给 nums 排序 */
vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, int target) {int sz = nums.size();
    vector<vector<int>> res;
    // 至多是 2Sum，且数组大小不应该小于 n
    if (n < 2 || sz < n) return res;
    // 2Sum 是 base case
    if (n == 2) {
        // 双指针那一套操作
        int lo = start, hi = sz - 1;
        while (lo < hi) {int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if (sum < target) {while (lo < hi && nums[lo] == left) lo++;
            } else if (sum > target) {while (lo < hi && nums[hi] == right) hi--;
            } else {res.push_back({left, right});
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
    } else {// n > 2 时，递归计算 (n-1)Sum 的后果
        for (int i = start; i < sz; i++) {
            vector<vector<int>> 
                sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (vector<int>& arr : sub) {// (n-1)Sum 加上 nums[i] 就是 nSum
                arr.push_back(nums[i]);
                res.push_back(arr);
            }
            while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
        }
    }
    return res;
}

嗯，看起来很长，实际上就是把之前的题目解法合并起来了，n == 2 时是 twoSum 的双指针解法，n > 2 时就是穷举第一个数字，而后递归调用计算 (n-1)Sum，组装答案。

须要留神的是，调用这个 nSum 函数之前肯定要先给 nums 数组排序 ，因为 nSum 是一个递归函数，如果在 nSum 函数里调用排序函数，那么每次递归都会进行没有必要的排序，效率会非常低。

比如说当初咱们写 LeetCode 上的 4Sum 问题：

vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());
    // n 为 4，从 nums[0] 开始计算和为 target 的四元组
    return nSumTarget(nums, 4, 0, target);
}

再比方 LeetCode 的 3Sum 问题，找 target == 0 的三元组：

vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());
    // n 为 3，从 nums[0] 开始计算和为 0 的三元组
    return nSumTarget(nums, 3, 0, 0);        
}

那么，如果让你计算 100Sum 问题，间接调用这个函数就完事儿了。

正文完