इस समस्या में, हमें अद्वितीय पूर्णांकों की एक सरणी और एक योग दिया गया है। और हमें उन ट्रिपलेट को ढूंढना है जो समान योग बना सकते हैं।
समस्या को हल करने के लिए एक उदाहरण लेते हैं -
इनपुट: सरणी = {0 , 2 , -1 , 1, -2} योग = 1 आउटपुट: 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; } } } } } // ड्राइवर कोड 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
इस विधि को सरणी को क्रमबद्ध करके और अधिक प्रभावी बनाया जा सकता है जो कोड की स्थान जटिलता को कम करेगा।
