Contains Duplicates

219. Contains Duplicates II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

给一个数组, 看nums[i]附近的k个数里, 是否有相同的. 也就是说, 如果存在nums[i] == nums[j]和abs(j-i) <= k则返回True 否则返回 False.

思路

从前往后去扫描一个数组, 用一个hashtable去记住每个数组出现的index. 如果有相同的, 则看hashtable中的记录和当前的index的是否再k以内, 如果是, 就返回True. 否则更新hashtable中的值.

Code

def containsDuplicate(nums, k):
    ht = dict()
    for i in range(len(nums)):
        if nums[i] not in ht:
            ht[nums[i]] = i
        else:
            if i - ht[nums[i]] <= k:
                return True
            ht[nums[i]] = i
    return False

时间复杂度

$O(n)$