18 四数之和
把之前两数之和和三数之和的通用框架方法总结一下,我们会发现:
实际上通用框架的思路就是,假设要求n数之和,那么:
- 首先遍历第一个数
nums[i],计算target - nums[i] - 求n - 1数之和,其
target(new)为target - nums[i],start为i + 1,得到结果集tuples - 将tuples中的每个结果tuple都添加
nums[i],放入新的结果集ans,最后返回即可 - 注意
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);
}
};
当然这只是通用框架的写法,方便记忆,可以把过程都展开为迭代等等