【LeetCode】题解 - nSumTarget 问题

57 阅读 0 评论 38 点赞

我是靠谱客的博主负责小蚂蚁，最近开发中收集的这篇文章主要介绍【LeetCode】题解 - nSumTarget 问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

从帅张星球，认识的 labuladong ，东哥曾带领着我们一众近 300 人，进行了为期 21 天的算法挑战，虽艰难，但始终坚持下来了（毕竟是立了军令状，而且与钱有关）。最近开始坚持系统学算法，重新学习了 labuladong 的 nSumTarget 模板，很受启发，尤其是模板思维。

无论是最近组织【九日集训】的英雄哪里出来，还是曾经 21 天算法挑战营的主理人 labuladong，都是前辈巨人。总能给我们的成长以加持，也总希望算法这条路，后来者居上~ 。

本文，是我学习 labuladong 公众号文章 - 《一个函数秒杀 2Sum 3Sum 4Sum 问题》之后，根据自己的理解整理而来，大家可以直接点击链接中的文章，去学习，相信看完都会忍不住加关注的。

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2:

输入：nums = [3,2,4], target = 6
输出：[1,2]

数据提示:

2 <= nums.length <= 104
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解法1：双层循环 O(N^2)

略。

解法2：排序 + 左右指针 O(N) + O(LogN)

使用映射或两个数组，将索引和元素值一起排序，保证索引和元素值的对应关系和顺序，元素值数组 - 左右指针，查找和为 target 的元素值对，返回下标，在索引值数组中，找到初始时，对应下标，返回即可。

解法3：查找表 - 哈希表 O(N)

在哈希表中查找 target - nums[i]，存在就返回索引对，不存在就放入

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 构建 record 
unordered_map<int, int> record;
for(int i = 0; i < nums.size(); i++) {
auto it = record.find(target - nums[i]); // 记录当前值
if(it != record.end()) {
// 找到就直接返回
return {it->second, i};
}
record[nums[i]] = i;
}
return {};
}
};

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列（升序），请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

每个输入只对应唯一的答案 ，而且不可以重复使用相同的元素。解决方案必须只使用常量级的额外空间。

示例 1:

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2:

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

数据提示:

2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
-1000 <= target <= 1000
只会存在一个有效答案

前文中 1. 两数之和的解法 1、3 依然有效。但不满足常量级辅助空间的要求。唯解法 2 可满足，考虑到本题中数组有序且答案唯一，直接上指针对撞即可，不用考虑诸如多个解、重复解等问题。

class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
// 暴力枚举，TIMEOUT →
未充分利用数组有序的特点
// 解法2：Two pointers O(N)
// 注意：返回结果中，索引是从 1 开始的
int N = numbers.size();
int lo = 0, hi = N -1;
while(lo < hi) {
int sum = numbers[lo] + numbers[hi];
if(sum > target) {
hi --;
} else if(sum < target) {
lo ++;
} else {
return {lo + 1, hi + 1};
}
}
throw std::invalid_argument("The input has no solution");
}
};

按照 labuladong 文章的递进顺序，魔改本题：nums 无序，满足和为 target 的解有多个，返回所有的解。并为了向后兼容三数之和，新的 twoSum 函数签名如下：

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

完整代码如下：

// 数组传入之前 排序，避免后续 三数之和 问题，在循环中，调用本方法，导致 n 次排序操作
vector<vector<int>> twoSumTarget(vector<int>& nums, int startIndex, int target) {
int lo = startIndex, hi = nums.size() - 1;
vector<vector<int>> res;
// 保存所有和为 target 的元素对
while(lo < hi) {
int left = nums[lo], right = nums[hi];
int sum = left + right;
if(sum < target) {
// lo ++。同时跳过所有重复的 nums[lo]
while(lo < hi && nums[lo] == left) lo ++;
} else if(sum > target) {
// hi --。同时跳过所有重复的 nums[hi]
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;
}

那么，167. 两数之和 II 的解法为：

class Solution {
public:
vector<vector<int>> twoSumTarget(vector<int>& nums, int startIndex, int target) {
int lo = startIndex, hi = nums.size() - 1;
vector<vector<int>> res;
// 保存所有和为 target 的元素对
while(lo < hi) {
// code ...
}
return res;
}
vector<int> twoSum(vector<int>& numbers, int target) {
// nums 有序，解唯一
return twoSumTarget(nums, 0, target)[0];
}
};

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1:

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2:

输入：nums = [0]
输出：[]

数据提示:

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

话接上文，将三数之和问题，拆解成寻找第一个数 nums[i] 和剩余两数之和 ltarget - nums[i]解的问题。此题 target 为 0，我们保留 target 参数，让题解更通用。

// 数组传入之前 排序，避免枚举第一个数时，多次调用本方法，导致 n 次排序操作
vector<vector<int>> threeSumTarget(vector<int>& nums, int startIndex, int target) {
int N = nums.size();
vector<vector<int>> res;
// 穷举 threeSum 的第一个数
for(int i = startIndex; i < N; i++) {
// 对 target - nums[i] 计算 twoSum
vector<vector<int>> tuples = twoSumTarget(nums, i + 1, target - nums[i]);
for(auto& tup : tuples) {
tup.push_back(nums[i]);
// 将满足的 nums[i] push_back 构成 三元组
res.push_back(tup);
// 将三元组 push_back 到 res 中
}
// 跳过第一个元素的重复
while(i < N - 1 && nums[i] == nums[i+1]) i ++;
}
return res;
}

那么，三数之和问题的解，如下：

class Solution {
public:
vector<vector<int>> twoSumTarget(vector<int>& nums, int startIndex, int target) {
int lo = startIndex, hi = nums.size() - 1;
vector<vector<int>> res;
// 保存所有和为 target 的元素对
while(lo < hi) {
// code ...
}
return res;
}
// 数组传入之前 排序，避免枚举第一个数时，多次调用本方法，导致 n 次排序操作
vector<vector<int>> threeSumTarget(vector<int>& nums, int startIndex, int target) {
int N = nums.size();
vector<vector<int>> res;
// 穷举 threeSum 的第一个数
for(int i = startIndex; i < N; i++) {
// code ...
}
return res;
}
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
return threeSumTarget(nums, 0, 0);
}
};

18. 四数之和

将四数之和问题，拆解成寻找第一个数 nums[i] 和剩余三数之和 ltarget - nums[i]解的问题。
将三数之和问题，拆解成寻找第一个数 nums[i] 和剩余两数之和 ltarget - nums[i]解的问题。
两数之和问题，已求解。

OK，见到递归，归纳如下：

当 (n-1)Sum 问题已求解时，nSum 问题拆解成寻找第一个数 nums[i] 和剩余(n-1) 数之和 target - nums[i] 解的问题；
当 n = 2 时，问题已求解。

nSumTarget 函数签名如下：
vector<vector<int>> nSumTarget(vector<int>& nums, int n, int startIndex, int target)

nums：已排序的数组；
n：组成和的数字个数。fourSum，n 为 4；
startIndex：左侧索引位（左右指针 lo 的初始值）；
target：和；

完整代码如下：

vector<vector<int>> nSumTarget(vector<int>& nums, int n, int startIndex, int target) {
// 将 nums 排序的操作 放在外面，避免寻找第一个数字之时，n 次的 sort 操作
assert(is_sorted(nums.begin(), nums.end()));
int sz = nums.size();
vector<vector<int>> res;
// 如果组成 target 的元素个数 n 小于 2 或者 nums 元素不足 n 个，直接返回
if(n < 2 || sz < n) return res;
if(n == 2) { // 递归的归处，最小待解决的问题 base case → twoSum 
int lo = startIndex, hi = sz - 1;
while(lo < hi) {
int left = nums[lo], right = nums[hi];
int sum = left + right;
if(sum > target) {
while(lo < hi && nums[hi] == right) hi --;
} else if(sum < target) {
while(lo < hi && nums[lo] == left) lo ++;
} else {
// 满足的数对，添加到 res 中
res.push_back( {left, right} );
while(lo < hi && nums[hi] == right) hi --;
while(lo < hi && nums[lo] == left) lo ++;
}
}
} else {
// n > 2时，返回 (n-1)Sum 的结果
for(int i = startIndex; i < sz; i++) {
vector<vector<int>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for(auto& arr : sub) {
arr.push_back(nums[i]);
res.push_back(arr);
}
// nums[i] 重复问题
while(i < sz - 1 && nums[i] == nums[i+1]) i++;
}
}
return res;
}

由此，四数之和问题的解，如下：

class Solution {
public:
// 传入的 nums 必须有序
vector<vector<int>> nSumTarget(vector<int>& nums, int n, int startIndex, int target) {
// code ...
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 数组排序
sort(nums.begin(), nums.end());
return nSumTarget(nums, 4, 0, target);
}
};