题目描述
给定一个整数数组和一个整数 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
