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(vector<int> &nums, int k) {
        const int n = nums.size();

        unordered_set<int> window;
        for (int i = 0; i < n; ++i) {
            if (window.count(nums[i])) {
                return true;
            }

            window.insert(nums[i]);
            if (i >= k) {
                window.erase(nums[i - k]);
            }
        }

        return false;
    }
};