資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的四數之和
假設我們有一個數字陣列。它儲存 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，則
- left := start right := 陣列大小 – 1
- 定義另一個大小為 2 的陣列 temp
- 當 left < right 時
- 如果 arr[left] + arr[right] = target，則
- temp[0] := arr[left]，temp[1] := arr[right]，並將 temp 插入 res
- 當 left < right 且 arr[left] = arr[left + 1] 時
- 將 l 增加 1
- 當 left < right 且 arr[right] = arr[right – 1] 時
- 將 r 減小 1
- 將 l 增加 1 並將 r 減小 1
- 否則，如果 arr[left] + arr[right] > target，則將 right 減小 1
- 否則，將 left 增加 1
- 如果 arr[left] + arr[right] = target，則
- 否則
- 對於 i 的範圍從 start 到陣列大小 – k
- 如果 i > start 且 arr[i] = arr[i - 1]，則跳過下一步並繼續
- 定義一個二維陣列 temp := kSum(arr, i + 1, k – 1, target – arr[i])
- 對於 j 的範圍從 0 到 temp
- 在 temp[j] 之後插入 arr[i]
- 將 temp 的所有元素複製到 res
- 對於 i 的範圍從 start 到陣列大小 – k
- 返回 res
示例（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]]
更新於：2020年4月27日
475 次瀏覽
廣告