Contains Duplicate III
Intuition
Solution
class Solution:
def containsNearbyAlmostDuplicate(self, nums: 'List[int]', k: 'int', t: 'int') -> 'bool':
if t < 0:
return False
cache = {}
for index, num in enumerate(nums):
if index - k > 0:
bucket_id_remove = nums[index - k - 1] // (t + 1)
del cache[bucket_id_remove]
bucket_id = num // (t + 1)
if bucket_id in cache:
return True
if bucket_id - 1 in cache and abs(cache[bucket_id-1] - num) <= t:
return True
if bucket_id + 1 in cache and abs(cache[bucket_id+1] - num) <= t:
return True
cache[bucket_id] = nums[index]
return False