219. Contains Duplicate II

1. Description

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most 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. Solutions

Hash Table && Sliding Window

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

class Solution {
public:
    bool containsNearbyDuplicate(const vector<int>& nums, int k) {
        unordered_map<int, int> value_index;
        for (int i = 0; i < nums.size(); ++i) {
            if (value_index.find(nums[i]) != value_index.end()) {
                return true;
            }

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

        return false;
    }
};