題目描述

給定一個整數(shù)數(shù)組和一個整數(shù) k，判斷數(shù)組中是否存在兩個不同的索引 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
著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解題思路

方法一：

滑動窗口 嘗試后發(fā)現(xiàn)一直超時

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 中元素的個數(shù)。在大部分面試中你都不需要自己去實現(xiàn)一個 BST，所以把 BST 當成一個黑盒子就可以了。大部分的編程語言都會在標準庫里面提供這些常見的數(shù)據(jù)結構。在 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）
著作權歸作者所有。商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處。

方法三

使用樹結構可以把搜索時間降低為，但是依舊會超時，需要一個能夠在常量時間內完成 搜索，刪除，插入 操作的數(shù)據(jù)結構，那就是散列表。
使用 模擬哈希表

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() 函數(shù)創(chuàng)建一個無序不重復元素集，可進行關系測試，刪除重復數(shù)據(jù)，還可以計算交集、差集、并集等 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. 哈希表可以實現(xiàn)常數(shù)時間內的查找 修改 和刪除
2. python中可以使用 或 模擬哈希表