博文中会简要介绍Leetcode P0219题目分析及解题思路。

“Contains Duplicate II”是p0217的衍生题，同样也是一道比较简单的题目。根据题目要求，我们不难得出这道题考察的核心是哈希表和滑动窗口，由于要求下标之间的差最多为k，所以滑动窗口的长度固定在k。

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.

这道题解法的核心在于维护一个容量为k的哈希表，然后使用这个哈希表来确定在窗口长度为k的滑动窗口中是否存在重复元素。

我们使用left（左指针）和right（右指针）这两个指针来遍历数组没，每次right指针遍历到一个元素，如果哈希表中已经存在则返回true；如果不存在，那么需要分两种情况，一是哈希表没有填满，那么直接往哈希表中加入right指向的元素即可，二是哈希表已满，那么将滑动窗口中left指向的元素移除，然后加入right指向的元素即可。

以下是Java的题解代码实现。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> kNumSet = new HashSet<>();
        int left = 0, right = 0, N = nums.length;
        while (right < N) {
            if (right-left > k) {
                kNumSet.remove(nums[left++]);
            }
            
            if (kNumSet.contains(nums[right]))
                return true;
            
            kNumSet.add(nums[right++]);
        }
        
        return false;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> num_set;
        int left = 0, right = 0, N = nums.size();
        while (right < N) {
            if (right > left+k) {
                num_set.erase(nums[left++]);
            }
            
            if (num_set.count(nums[right]) > 0)
                return true;
            
            num_set.insert(nums[right++]);
        }
        
        return false;
    }
};