Giả sử chúng ta có một mảng số. Nó lưu trữ n số nguyên, có bốn phần tử a, b, c và d trong mảng. Chúng ta có một giá trị mục tiêu khác, sao cho a + b + c + d =mục tiêu. Tìm tất cả các bộ tứ duy nhất trong mảng thỏa mãn tình huống. Vì vậy, nếu mảng giống như [-1,0,1,2,0, -2] và đích là 0, thì kết quả sẽ là [[-1, 0, 0, 1], [- 2, -1, 1, 2], [-2, 0, 0, 2]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Tổng thực tế đang được thực hiện bằng cách sử dụng một hàm được gọi là kSum (). Điều này nhận mảng, bắt đầu, k và mục tiêu. Ban đầu hàm sẽ được gọi với k giá trị 4. Hàm sẽ như sau
- xác định res một mảng
- nếu k =2, thì
- left:=start và right:=array size - 1
- xác định nhiệt độ mảng khác có kích thước 2
- trong khi bên trái
- nếu arr [left] + arr [right] =target, thì
- temp [0]:=arr [left], temp [1]:=arr [right] và chèn tạm thời vào res
- while left
- tăng l thêm 1
- while left
- giảm r đi 1
- nếu arr [left] + arr [right] =target, thì
- tăng l thêm 1 và giảm r đi 1
- đối với tôi trong phạm vi bắt đầu đến kích thước arr - k,
- if i> start and arr [i] =arr [i - 1], sau đó bỏ qua các bước tiếp theo và tiếp tục
- xác định một nhiệt độ mảng 2d:=kSum (arr, i + 1, k - 1, target - arr [i])
- cho j trong phạm vi 0 đến nhiệt độ
- chèn arr [i] sau temp [j]
- sao chép tất cả các yếu tố tạm thời sang res
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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)); }
Đầu vào
[1,0,-1,0,-2,2] 0
Đầu ra
[[1,2,-1,-2],[0,2,0,-2],[0,1,0,-1]]