leetcode with python:219. Contains Duplicate II

题目:

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%)

那我们下题见