twoSum
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标.
nums
中可能有多对儿元素之和都等于 target
,请你的算法返回所有和为 target
的元素对儿,其中不能出现重复。
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;
}
3Sum
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = target ?请你找出所有和为 target 且不重复的三元组。
分析:
现在我们想找和为 target
的三个数字,那么对于第一个数字,可能是什么?nums
中的每一个元素 nums[i]
都有可能!
那么,确定了第一个数字之后,剩下的两个数字可以是什么呢?其实就是和为 target - nums[i]
的两个数字呗,那不就是 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
函数会保证它们不重复。所以代码中必须用一个 while 循环来保证 3Sum
中第一个元素不重复。
4Sum
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 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;
}
nSum
那么,如果我让你求 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;
}