class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if k < 1 or t < 0:
            return False
        dic = {}
        t += 1
        for i in range(len(nums)):
            if i > k:
                del dic[nums[i - k - 1] // t]
            m = nums[i] // t
            if m in dic:
                return True
            if m - 1 in dic and abs(nums[i] - dic[m - 1]) < t:
                return True
            if m + 1 in dic and abs(nums[i] - dic[m + 1]) < t:
                return True
            dic[m] = nums[i]
        return False

test = Solution()
print(test.containsNearbyAlmostDuplicate([1, 3, 1], 1, 1))
