Contains Duplicate II trong C++

Cho mảng nums và số k, kiểm tra có tồn tại i ≠ j sao cho nums[i] == nums[j] và |i - j| ≤ k.

Ví dụ: [1,2,4,1], k=3 → true (vị trí 0 và 3, khoảng cách 3).

Giải thuật (Sliding Window + HashSet)

1. Duyệt mảng, duy trì unordered_set chứa tối đa k phần tử gần nhất.
2. Nếu nums[i] đã có trong set → trả về true.
3. Thêm nums[i] vào set. Nếu size > k, xóa nums[i-k].

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> window;
        for (int i = 0; i < nums.size(); i++) {
            if (window.count(nums[i])) return true;
            window.insert(nums[i]);
            if (window.size() > k) window.erase(nums[i - k]);
        }
        return false;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,4,1};
    cout << boolalpha << ob.containsNearbyDuplicate(v, 3); // true
    return 0;
}

Đầu vào / Đầu ra

Input: {1,2,4,1}, 3
Output: true (1)