Kiểm tra trùng lặp gần nhau III trong C++

Cho mảng số nguyên, kiểm tra xem có tồn tại hai chỉ số khác nhau i và j sao cho:

• |nums[i] - nums[j]| <= t (chênh lệch giá trị không quá t).
• |i - j| <= k (khoảng cách chỉ số không quá k).

Ví dụ: nums = [1,2,3,1], k = 3, t = 0 → trả về true vì nums[0] = nums[3] = 1 và |0-3| = 3 <= k.

Thuật toán giải quyết (Cửa sổ trượt + Multiset)

1. Duy trì một multiset chứa tối đa k phần tử gần nhất.
2. Duyệt mảng từ trái sang phải:
• Tìm iterator x trỏ đến phần tử đầu tiên >= nums[i] (lower_bound).
• Nếu x tồn tại và *x <= nums[i] + t → trả về true.
• Nếu x không phải phần tử đầu tiên, kiểm tra phần tử trước đó (prev(x)): nếu *prev(x) + t >= nums[i] → trả về true.
• Chèn nums[i] vào multiset.
• Nếu kích thước multiset > k → xóa nums[i - k].
3. Kết thúc vòng lặp → trả về false.

Ví dụ minh họa (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 x = s.lower_bound((long long)nums[i] - t);
            if (x != s.end() && *x <= (long long)nums[i] + t) return true;
            s.insert(nums[i]);
            if ((int)s.size() > 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);
}

Đầu vào

[1,2,3,1] 3 0

Đầu ra

1