题目描述

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

此题思路，可以通过两次循环找出答案，时间复杂度为O(n^2)

更为高效的思路则为如果索引差值最大不超过k，则可以寻找一片空间，空间最大可以包含k+1个元素（例如：k=2，则空间最多可以包含0,1,2三个索引对应的值）我们寻找在这个空间里是否有k+1的下一个元素，如果有，直接返回，如果没有，我们让k+1这个指针往右移动1，最前面的那个元素可以直接删除

以下为python代码

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        order_set = set()
        
        for i in range(len(nums)):
            if nums[i] in order_set:
                return True
            order_set.add(nums[i])
            # 保持record中最多有k个元素
            if len(order_set) == k + 1:
                order_set.remove(nums[i-k]) 

        return False