C ++中的4Sum
假设我们有一个数字数组。它存储n个整数，数组中有四个元素a，b，c和d。我们有另一个目标值，即a+b+c+d=目标。在满足条件的数组中找到所有唯一的四元组。因此，如果数组类似于[-1,0,1,2,0，-2]并且目标为0，则结果将为[[-1，0，0，1]，[-2，-1，1，2]，[-2，0，0，2]]
为了解决这个问题，我们将遵循以下步骤-
实际的总和是使用称为的函数来完成的kSum()。这需要数组，开始，k和目标。最初将使用k值4调用该函数。该函数如下
定义数组res
如果k=2，则
如果arr[left]+arr[right]=目标，则
否则，如果arr[left]+arr[right]>目标，则向右减少1
否则增加1
将r减1
使我增加1
temp[0]：=arr[left]，temp[1]：=arr[right]，然后将temp插入res
而left<right和arr[left]=arr[left+1]
而左<右和arr[right]=arr[right–1]
将l增加1并将r减少1
左：=开始，右：=数组大小–1
定义大小为2的另一个数组温度
而左<右
其他
如果i>开始并且arr[i]=arr[i-1]，则跳过下一步并继续
定义一个2d数组temp：=kSum（arr，i+1，k–1，target–arr[i]）
对于介于0到temp的j
将temp的所有元素复制到res
在temp[j]之后插入arr[i]
因为我在范围内开始到arr大小–k，
返回资源
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
void addAll(vector < vector <int> >& res, vector < vector <int> >& temp){
for(int i = 0; i < temp.size(); i++)res.push_back(temp[i]);
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
return kSum(nums, 0, 4, target);
}
vector < vector <int> > kSum(vector <int>& arr, int start, int k, int target){
vector < vector <int> > res;
if(k == 2){
int left = start;
int right = arr.size() - 1;
vector <int> temp(2);
while(left < right){
if(arr[left] + arr[right] == target){
temp[0] = arr[left];
temp[1] = arr[right];
res.push_back(temp);
while(left < right && arr[left] == arr[left + 1])left++;
while(left < right && arr[right] == arr[right - 1])right--;
left++;
right--;
}
else if(arr[left] + arr[right] > target)right--;
else left ++;
}
}
else{
for(int i = start; i < (int)arr.size() - k + 1; i++){
if(i > start && arr[i] == arr[i - 1])continue;
vector < vector <int> > temp = kSum(arr, i + 1, k - 1, target - arr[i]);
for(int j = 0; j < temp.size(); j++){
temp[j].push_back(arr[i]);
}
addAll(res, temp);
}
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,0,-1,0,-2,2};
print_vector(ob.fourSum(v, 0));
}输入值
[1,0,-1,0,-2,2] 0
输出结果
[[1,2,-1,-2],[0,2,0,-2],[0,1,0,-1]]