題目描述

給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k吮旅，判斷數(shù)組中是否存在兩個(gè)不同的索引 i 和 j枣申，使得 nums [i] = nums [j]本辐，并且 i 和 j 的差的絕對(duì)值最大為 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有砂蔽。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)碑定，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處流码。

解題思路

方法一：

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

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

方法二

方法一中消耗時(shí)間在于每次在窗口內(nèi)搜索成次方增長(zhǎng)，窗口越長(zhǎng)時(shí)間增長(zhǎng)越快延刘。而能降低搜索時(shí)間的方法在于排序漫试。使窗口內(nèi)的元素都是排序的，那么搜索時(shí)自然能夠降低為碘赖。
那么就需要維持一個(gè)排序了的窗口驾荣。

一個(gè)更好的選擇是使用自平衡二叉搜索樹（BST)。 BST 中搜索普泡，刪除播掷，插入都可以保持 O(log?k)O(\log k)O(logk) 的時(shí)間復(fù)雜度，其中 kkk 是 BST 中元素的個(gè)數(shù)撼班。在大部分面試中你都不需要自己去實(shí)現(xiàn)一個(gè) BST歧匈，所以把 BST 當(dāng)成一個(gè)黑盒子就可以了。大部分的編程語(yǔ)言都會(huì)在標(biāo)準(zhǔn)庫(kù)里面提供這些常見的數(shù)據(jù)結(jié)構(gòu)砰嘁。在 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）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)板祝，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處宫静。

方法三

使用樹結(jié)構(gòu)可以把搜索時(shí)間降低為，但是依舊會(huì)超時(shí)，需要一個(gè)能夠在常量時(shí)間內(nèi)完成 搜索孤里，刪除伏伯，插入 操作的數(shù)據(jù)結(jié)構(gòu)，那就是散列表捌袜。
使用 模擬哈希表

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)建一個(gè)無序不重復(fù)元素集说搅，可進(jìn)行關(guān)系測(cè)試，刪除重復(fù)數(shù)據(jù)虏等，還可以計(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

總結(jié)

1. 哈希表可以實(shí)現(xiàn)常數(shù)時(shí)間內(nèi)的查找 修改 和刪除
2. python中可以使用 或 模擬哈希表