এই সমস্যায়, ইউনিক ইন্টিজারগুলোর একটি অ্যারে এবং একটি যোগফল দেওয়া থাকে। এবং আমাদের যেসব ট্রিপলেট সেই যোগফল তৈরি করে সেগুলো খুঁজে বের করতে হবে।
উদাহরণ দিয়ে সমাধান বুঝি:
ইনপুট: array = {0, 2, -1, 1, -2} Sum = 1 আউটপুট: 1 2 -2 0 2 -1এই সমস্যাটি সমাধান করার জন্য, আমরা যোগফল দেওয়া সব ট্রিপলেট খুঁজে বের করব। একটি সহজ পদ্ধতি হবে তিনটি লুপ ব্যবহার করে এলিমেন্টগুলোর যোগফল বের করা এবং যথাযথ ট্রিপলেট রিটার্ন করা।
C++ উদাহরণ
#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³) হবে। তাই আমরা অন্য টেকনিক ব্যবহার করব এই সমস্যাটি দক্ষতার সাথে সমাধান করার জন্য।
একটি পদ্ধতি হলো হ্যাশিং ব্যবহার করা। এই মেথডে, আমরা প্রতিটি এলিমেন্টের জন্য এমন পেয়ার খুঁজে বের করব যাতে সেগুলো একে অপরের কমপ্লিমেন্ট होয় অর্থাৎ 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
এই মেথডটি আরও দক্ষ করা যায় অ্যারেটি সর্ট করে যা কোডের স্পেস কমপ্লেক্সিটি কমিয়ে দেবে।
