動機

從 數量 或 距離

Problem

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.

 

Example 1:

Input: nums = [1,2,3,1], k = 3Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2Output: false

 

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

Sol: 數量

用hash把一個範圍內的所有數字做統計

class Solution:
    def f(self,i):
        return any([self.ns[i] == self.ns[j] for j in range(i+1,min(i+self.k+1,len(self.ns)))])
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        self.ns = nums
        self.k = k
        tbl = Counter(nums[:k+1])
        for i in range(len(nums)):
            #print("before",tbl)
            if tbl.get(nums[i],0) > 1:
                return True
            if nums[i] in tbl and tbl[nums[i]] > 0:
                tbl[nums[i]] -= 1
            
            if i+k+1 < len(nums):
                tbl[nums[i+k+1]] = tbl.get(nums[i+k+1],0)+1
            #print("after",tbl)
        return False

Case study: 距離

用hash把數字的index記錄下來，等下次遇到時算距離

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if not nums: return False
        counts = {}
        for i,n in enumerate(nums):
            if n in counts and i-counts[n] <= k:
                return True
            else:
                counts[n] = i
        return False