Leetcode 220. Contains Duplicate III

https://leetcode.com/problems/contains-duplicate-iii/

Window and bucket!

if： | nums[i] - nums[j] | <= t
namely： | nums[i] / t - nums[j] / t | <= 1
then： | floor(nums[i] / t) - floor(nums[j] / t) | <= 1
​therefore： floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1}

Solution:

# T:O(n*t) S:O(max(k,t))
class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @param {integer} t
    # @return {boolean}
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if k < 0 or t < 0:
            return False
        window = collections.OrderedDict()
        for n in nums:
            # Make sure window size
            if len(window) > k:
                window.popitem(False)
                
            bucket = n if not t else n // t
            # At most 2t items.
            for m in (window.get(bucket - 1), window.get(bucket), window.get(bucket + 1)):
                if m is not None and abs(n - m) <= t:
                    return True
            window[bucket] = n
        return False

Run Time: 144 ms