সমস্যা বিবরণ
একটি অ্যারে nums (nটি পূর্ণসংখ্যা) এবং একটি target দেওয়া আছে। nums-এ তিনটি পূর্ণসংখ্যা খুঁজে বের করতে হবে যাদের যোগফল target-এর সবচেয়ে কাছাকাছি। সেই তিনটি সংখ্যার যোগফল রিটার্ন করতে হবে। ধরে নেওয়া হয় প্রতিটি ইনপুটের একটিমাত্র সমাধান আছে।
উদাহরণ: অ্যারে = [-1,2,1,-4], target = 1 হলে ট্রিপলেট [-1,2,1] যেন যোগফল ২, যা target-এ সবচেয়ে কাছাকাছি।
সমাধানের ধাপসমূহ
- অ্যারে সো্র্ট করুন, ans := 0, diff := Infinity, n := nums.size()।
- i = 0 থেকে n-1 পর্যন্ত লুপ করুন:
- left := i+1, right := n-1
- যখন left < right:
- temp := nums[left] + nums[right] + nums[i]
- যদি |target - temp| < diff হয়, তবে ans := temp এবং diff := |target - temp|
- যদি temp == target হয়, তবে temp রিটার্ন করুন, অন্যথায় temp > target হলে right--, অন্যথায় left++
- ans রিটার্ন করুন।
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;
}
};
int main() {
Solution ob;
vector<int> v = {-1,2,1,-4};
cout << ob.threeSumClosest(v, 1);
}
ইনপুট
[-1,2,1,-4] 1
আউটপুট
2
