इस समस्या में, हमें अद्वितीय पूर्णांकों की एक सरणी और एक योग दिया जाता है। और हमें उन त्रिगुणों को खोजना है जो समान योग बना सकते हैं।
आइए समस्या को हल करने के लिए एक उदाहरण लेते हैं -
Input : array = {0 , 2 , -1 , 1, -2}
Sum = 1
Output : 1 2 -2
0 2 -1 इस समस्या को हल करने के लिए, हम योग प्रदान करने वाले सभी त्रिक ज्ञात करेंगे। एक आसान तरीका तीन लूपों का उपयोग करना और तत्वों का योग ज्ञात करना और पर्याप्त त्रिक लौटाना होगा।
उदाहरण
#include <iostream>
using namespace std;
void Triplets(int arr[], int n, int sum){
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
cout<<arr[i]<<"\t"<<arr[j]<<"\t"<<arr[k]<<endl;
}
}
}
}
}
// Driver code
int main(){
int arr[] = { 0 , 2 , -1 , 1, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The Triplets are : \n";
Triplets(arr, n, 1);
return 0;
} आउटपुट
त्रिक हैं -
0 2 -1 2 1 -2
लेकिन यह दृष्टिकोण कुशल नहीं है क्योंकि इसमें o(n 3 .) की समय जटिलता होगी ) तीन लूप चलाने के लिए। इसलिए, हम इस समस्या को प्रभावी तरीके से हल करने के लिए अन्य तकनीकों का उपयोग करेंगे।
एक विधि हैशिंग का उपयोग कर रही है। इस पद्धति में, हम प्रत्येक तत्व के जोड़े ऐसे पाएंगे कि वे एक दूसरे के पूरक हैं यानी मान x वाले तत्व के लिए, हमें एक तत्व -x की आवश्यकता है।
यह कोड की समय जटिलता को कम करता है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void Triplets(int arr[], int n, int sum{
for (int i = 0; i < n - 1; i++) {
unordered_set<int> triplet;
for (int j = i + 1; j < n; j++) {
int third = sum - (arr[i] + arr[j]);
if (triplet.find(third) != triplet.end())
cout<<third<<"\t"<<arr[i]<<"\t"<<arr[j]<<endl;
else
triplet.insert(arr[j]);
}
}
}
int main(){
int arr[] = { 0 , 2 , -1 , 1, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The Triplets are : \n";
Triplets(arr, n, 1);
return 0;
} आउटपुट
त्रिक हैं -
0 2 -1 2 1 -2
इस पद्धति को सरणी को क्रमबद्ध करके और अधिक प्रभावी बनाया जा सकता है जिससे कोड की स्थान जटिलता कम हो जाएगी।