একটি পূর্ণসংখ্যার অ্যারে দেওয়া থাকলে, দুটি ভিন্ন ইনডেক্স i এবং j খুঁজে বের করতে হবে যাতে |nums[i] - nums[j]| <= t এবং |i - j| <= k।
উদাহরণ: nums = [1,2,3,1], k = 3, t = 0 হলে আউটপুট true।
সমাধানের ধাপসমূহ
- একটি মাল্টিসেট
sব্যবহার করুন। - প্রতিটি উপাদানের জন্য
lower_boundদিয়ে সবচেয়ে কাছের বড় বা সমান মান খুঁজুন। - যদি পার্থক্য
<= tহয়,trueরিটার্ন করুন। - পূর্বের উপাদানও চেক করুন।
- সেটে বর্তমান উপাদান যোগ করুন এবং
i >= kহলেnums[i-k]মুছে দিন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
multiset<long long> s;
int n = nums.size();
for (int i = 0; i < n; i++) {
auto it = s.lower_bound((long long)nums[i] - t);
if (it != s.end() && *it - nums[i] <= t) return true;
s.insert(nums[i]);
if (i >= k) s.erase(nums[i - k]);
}
return false;
}
};
int main() {
Solution ob;
vector<int> v = {1, 2, 3, 1};
cout << ob.containsNearbyAlmostDuplicate(v, 3, 0);
}
ইনপুট
[1,2,3,1] 3 0
আউটপুট
1
