题目描述
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
方法一：
滑动窗口 尝试后发现一直超时
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
if k < 0: return False
for i in range(len(nums)):
for j in range(i+1,i+k+1):
if j < len(nums):
if nums[i] == nums[j] :
return True
else :
break
return False
方法二
方法一中消耗时间在于每次在窗口内搜索成次方增长，窗口越长时间增长越快。而能降低搜索时间的方法在于排序。使窗口内的元素都是排序的，那么搜索时自然能够降低为
。
那么就需要维持一个排序了的窗口。
一个更好的选择是使用自平衡二叉搜索树（BST)。 BST 中搜索，删除，插入都可以保持 O(logk)O(\log k)O(logk) 的时间复杂度，其中 kkk 是 BST 中元素的个数。在大部分面试中你都不需要自己去实现一个 BST，所以把 BST 当成一个黑盒子就可以了。大部分的编程语言都会在标准库里面提供这些常见的数据结构。在 Java 里面，你可以用 TreeSet 或者是 TreeMap。在 C++ STL 里面，你可以用 std::set 或者是 std::map。
作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/cun-zai-zhong-fu-yuan-su-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法三
使用树结构可以把搜索时间降低为，但是依旧会超时，需要一个能够在常量时间内完成 搜索，删除，插入 操作的数据结构，那就是散列表。
使用 模拟哈希表
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
if k < 0: return False
map = dict()
for i in range(len(nums)):
if nums[i] in map and i - map[nums[i]] <= k:
return True
map[nums[i]] = i
return False
还可以使用
set() 函数创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等 https://www.runoob.com/python/python-func-set.html
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
s = set([])
for i in range(len(nums)):
if nums[i] in s:
return True
s.add(nums[i])
if len(s) > k:
s.remove(nums[i-k])
return False
总结
- 哈希表可以实现常数时间内的查找 修改 和删除
- python中可以使用
或
模拟哈希表
