ধরুন আমাদের n পূর্ণসংখ্যা এবং একটি লক্ষ্য সহ একটি অ্যারে সংখ্যা রয়েছে। আমাদেরকে সংখ্যায় তিনটি পূর্ণসংখ্যা খুঁজে বের করতে হবে যাতে যোগফল টার্গেটের সবচেয়ে কাছাকাছি হয়। আমরা তিনটি পূর্ণসংখ্যার যোগফল ফেরত দেব। আমরা একটি অনুমান নিতে পারি যে প্রতিটি ইনপুটের ঠিক একটি সমাধান থাকবে। সুতরাং যদি প্রদত্ত অ্যারেটি [-1,2,1,-4] এর মত হয় এবং লক্ষ্য 1 হয়, তাহলে ট্রিপলেটটি হবে [-1,2,1] এর নিকটতম যোগফল, অর্থাৎ 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- অ্যারের সংখ্যাগুলি সাজান, উত্তর :=0, পার্থক্য :=ইনফিনিটি, n :=সংখ্যার আকার
- আমি 0 থেকে n – 1
- পরিসরে
- বামে :=i + 1, ডানে :=n – 1
- যখন বাম
- temp :=nums[left] + nums[right] + nums[i]
- যদি |টার্গেট – টেম্প|
- যদি temp =টার্গেট হয়, তাহলে temp রিটার্ন করুন, অন্যথায় যখন temp> টার্গেট হয়, তখন ডানে 1 কমিয়ে দিন, অন্যথায় বাঁদিকে 1 দিয়ে বাড়ান
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = 0;
int diff = INT_MAX;
int n = nums.size();
for(int i = 0; i < n; i++){
int left = i + 1;
int right = n - 1;
while(left < right){
int temp = nums[left] + nums[right] + nums[i];
if(abs(target - temp) < diff){
ans = temp;
diff = abs(target - temp);
}
if(temp == target)return temp;
else if(temp > target) right--;
else left++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {-1,2,1,-4};
cout << ob.threeSumClosest(v, 1);
} ইনপুট
[-1,2,1,-4] 1
আউটপুট
2
