题目描述

给定一个整数数组和一个整数 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(log⁡k)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

图片.png

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

总结

1. 哈希表可以实现常数时间内的查找 修改 和删除
2. python中可以使用 或 模拟哈希表