题目

给你一个整数数组nums和一个整数k，判断数组中是否存在两个不同的索引i和j，满足nums[i] == nums[j]且abs(i - j) <= k。如果存在，返回true；否则，返回false。 

来源：力扣（LeetCode）

解答

主体思路就是利用滑动窗口，滑动窗口大小为k，即保证窗口内的索引差值 <= k；

起始时，由于窗口内元素少于k，直接将遍历的数组元素放入到哈希集合中即可；

当滑动窗口中元素个数超过k个后，需要将滑动窗口最左侧下标元素移除（这里可以利用一个l变量来保存最左侧元素下标），然后再插入遍历到的元素。

且在将元素插入到哈希集合时，进行重复元素检查，如果当前滑动窗口内的哈希集合存在新插入的元素，表明符合题意，直接返回true即可；

如果遍历完毕后，都没有找到重复的元素，则直接返回false即可。

代码如下：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int> &nums, int k) {
        int n = nums.size();
        unordered_set<int> st;
        int l = 0;

        // 将前 k+1 个元素加入集合
        for (int i = 0; i < n && i < k + 1; ++i) {
            auto it = st.find(nums[i]);
            if (it != st.end()) {
                return true;
            }
            st.insert(nums[i]);
        }

        // 从第 k+2 个元素开始遍历
        for (int r = k + 1; r < n; ++r) {
            st.erase(nums[l++]);
            auto it = st.find(nums[r]);
            if (it != st.end()) {
                return true;
            }
            st.insert(nums[r]);
        }

        return false;
    }
};

精简版：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int> &nums, int k) {
        int n = nums.size();
        unordered_set<int> st;

        int l = 0;
        for (int r = 0; r < n; ++r) {
            if (r > k) {
                st.erase(nums[l++]);
            }
            auto it = st.find(nums[r]);
            if (it != st.end()) {
                return true;
            }
            st.insert(nums[r]);
        }

        return false;
    }
};

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        st = set()
        l = 0
        
        for i in range(len(nums)):
            if i > k:
                st.remove(nums[l])
                l += 1

            if nums[i] in st:
                return True
            st.add(nums[i])

        return False