219. Contains Duplicate II

1. Description

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

2. Example

Example 1

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

3. Constraints

• 1 <= nums.length <= $10^5$
• -$10^9$ <= nums[i] <= $10^9$
• 0 <= k <= $10^5$

4. Solutions

Hash Table && Sliding Window

n = nums.size()
Time complexity: O(n)
Space complexity: O(min(n, k))

class Solution {
public:
    bool containsNearbyDuplicate(const vector<int> &nums, int k) {
        const int n = nums.size();
        unordered_set<int> window_values;
        window_values.reserve(min(n, k + 1));
        for (int i = 0; i < n; ++i) {
            if (i > k) {
                window_values.erase(nums[i - k - 1]);
            }

            if (window_values.count(nums[i]) > 0) {
                return true;
            }

            window_values.insert(nums[i]);
        }

        return false;
    }
};