এই সমস্যায়, আমাদেরকে অনন্য পূর্ণসংখ্যার একটি অ্যারে এবং একটি যোগফল দেওয়া হয়েছে। এবং আমাদের খুঁজে বের করতে হবে ট্রিপলেট যা একইসাম গঠন করতে পারে।
সমস্যা সমাধানের জন্য একটি উদাহরণ নেওয়া যাক −
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
এই পদ্ধতিটি অ্যারে সাজানোর মাধ্যমে আরও কার্যকর করা যেতে পারে যা কোডের স্থান জটিলতা কমিয়ে দেবে।
