滑动窗口+哈希表

我们可以用一个窗口，窗口大小固定为k+1个元素，哈希表维护窗口内的每个数出现的次数。

每次判断窗口内的当前遍历的元素是否重复出现，重复出现返回true即可。

总结下固定滑动窗口的套路：

• 不需要双指针，从左到右遍历，每次先处理下当前元素
• 再判断最左边是否有元素滑出窗口（因为是固定窗口，遍历step是1，则每次滑出窗口至多是1）
• 最后判断下题目要求的条件。

时间复杂度$O(N)$，空间复杂度$O(N)$

AC代码

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        k ++;
        for (int i = 0 ; i < nums.size() ; i ++) {
            mp[nums[i]] ++;
            //窗口左边是否划出
            if (i - k + 1 > 0) mp[nums[i - k]] --;
            //窗口内是否有重复元素
            if (mp[nums[i]] >= 2)
                return true;
        }
        return false;
    }
};