# LeetCode Medium 220. Contains Duplicate III

tags: leetcode

問題

• Explore
• Problems

アイデア

整数の配列numsが与えられたとき，abs(nums[i] - nums[j]) <= tかつabs(i - j) <= kであるようなiとjがあるかを探せという問題です．

解法

• まずtは非負なのでその時点でFalseを返します
• 連想配列cache[numをt+1で割った商] = numを用意します．
  • $[0, t], [t + 1, 2t + 1], [2t + 2, 3t + 2]$と$t + 1$ごとで区切って連想配列内で記録します．計算を記録することで計算する回数を減らします．
  • 例えばt = 4でnum = 13とします．このときnumと絶対値の差があるのは9，17で，それぞれ5で割ったときの商は2，1, 3です．
  • これは必要条件で，この条件を満たす上でnum同士を比較します．
• 配列から要素をk回取り出すごとに余分な連想配列を削除します．

計算量

配列の要素の数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Python

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if t < 0:
            return False
        cache = {}
        for i in range(len(nums)):
            if i - k > 0:
                del cache[nums[i - k - 1] // (t+1)]
            bucket_id = nums[i] // (t+1)
            cond1 = bucket_id in cache
            cond2 = bucket_id-1 in cache and abs(cache[bucket_id-1] - nums[i]) <= t
            cond3 = bucket_id+1 in cache and abs(cache[bucket_id+1] - nums[i]) <= t
            if cond1 or cond2 or cond3:
                return True
            cache[bucket_id] = nums[i]
        return False