一个函数秒杀 nSum 问题
培养框架思维，真正爱上算法！关注公众号查看更新文章👆
相关推荐：
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
经常刷 LeetCode 的读者肯定知道鼎鼎有名的 twoSum 问题，我们旧文 twoSum 问题的核心思想 就对 twoSum 的几个变种做了解析。
但是除了 twoSum 问题，LeetCode 上面还有 3Sum，4Sum 问题，我估计以后出个 5Sum，6Sum 也不是不可能。
那么，对于这种问题有没有什么好办法用套路解决呢？
今天 labuladong 就由浅入深，层层推进，用一个函数来解决所有 nSum 类型的问题。
一、twoSum 问题
上篇文章 twoSum 问题的核心思想 写了力扣上的 2Sum 问题，题目要求返回的是索引，这里我来编一道 2Sum 题目：
如果假设输入一个数组 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 {lo, hi};
}
}
return {};
}
这样就可以解决这个问题，不过 labuladong 要魔改一下题目，把这个题目变得更泛华，更困难一点。
题目告诉我们可以假设 nums 中有且只有一个答案，且需要我们返回对应元素的索引，现在修改这些条件：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)。
二、3Sum 问题
这是 LeetCode 第 15 题：
题目就是让我们找 nums 中和为 0 的三个元素，返回所有可能的三元组（triple），函数签名如下：
vector<vector<int>> threeSum(vector<int>& nums);
这样，我们再泛化一下题目，不要光和为 0 的三元组了，计算和为 target 的三元组吧，同上面的 twoSum 一样，也不允许重复的结果：
＿＿＿＿＿＿＿＿＿＿＿＿＿
本文只能在 labuladong 公众号查看，关注后可直接搜索本站内容：
