題目:

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

給定一個陣列跟一數k,確認此陣列是否有重複的數且兩者在陣列中的距離小於等於k

這題我決定用sliding window去做
順便複習這個好久不見的演算法

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        s=set()
        i=0
        j=0
        while j<len(nums):
            if j-i<=k:
                if nums[j] not in s:
                    s.add(nums[j])
                    j=j+1
                else:
                    return True
            else:
                s.remove(nums[i])
                i=i+1
        return False

在一開始的位置,設立兩個指標
一個先往前走,將路過的值放入set,一旦兩指標相距超過k,另一個指標便要往前移,並將其原本位置的值從set移除
過程持續直到陣列末端,途中一旦發現要放入的值存在在set內,就回傳True
若到最後還是沒發現,就回傳False
最後執行時間645ms(faster than 91.42%)

當然也有hash map解
我這裡分享一個在討論區看到的解法

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        d={}
        for i in range(len(nums)):
            if nums[i] in d and i-d[nums[i]]<=k:
                return True
            d[nums[i]]=i
        return False

建立一個dictionary(d),紀錄值及他們的位置
若遇到值的位置-dictionary紀錄的位置<=k
那麼就回傳True
如果相差超過k,就刷新d所紀錄該值的位置(紀錄的值是要離遍歷中的指標最近的)
到最後都沒發現就回傳False
最後執行時間601ms(faster than 98.99%)

那我們下題見