मान लीजिए कि हमारे पास संख्याओं की एक सरणी है। यह 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 मान 4 के साथ कॉल किया जाएगा। फ़ंक्शन निम्नानुसार होगा
- एक सरणी रेस परिभाषित करें
- अगर के =2, तो
- बाएं:=प्रारंभ और दाएं:=सरणी आकार – 1
- आकार 2 की एक और सरणी अस्थायी परिभाषित करें
- बाएं <दाएं
- अगर गिरफ्तारी [बाएं] + गिरफ्तारी [दाएं] =लक्ष्य, तो
- temp[0] :=arr[left], temp[1] :=arr[right], और res में temp डालें
- बाएं <दाएं और एआर [बाएं] =गिरफ्तारी [बाएं + 1]
- 1 से l बढ़ाएँ
- बाएं <दाएं और एआर [दाएं] =एआर [दाएं - 1]
- r को 1 से घटाएं
- l को 1 से बढ़ाएं और r को 1 से घटाएं
- अन्यथा अगर गिरफ्तारी [बाएं] + गिरफ्तारी [दाएं]> लक्ष्य है, तो 1 से दाएं घटाएं
- अन्यथा शेष 1 की वृद्धि करें
- अगर गिरफ्तारी [बाएं] + गिरफ्तारी [दाएं] =लक्ष्य, तो
- अन्य
- के लिए मैं सीमा में आकार गिरफ्तार करने के लिए शुरू - k,
- अगर मैं> शुरू और गिरफ्तार करता हूं [i] =arr[i - 1], तो अगले चरणों को छोड़ दें और जारी रखें
- एक 2d सरणी अस्थायी परिभाषित करें:=kSum(arr, i + 1, k-1, target – arr[i])
- जे के लिए 0 से अस्थायी श्रेणी में
- अस्थायी[j] के बाद गिरफ्तारी [i] डालें
- टेम्परेचर के सभी तत्वों को res में कॉपी करें
- के लिए मैं सीमा में आकार गिरफ्तार करने के लिए शुरू - 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]]