Contains Duplicate III

Problem: Contains Duplicate III

Actually I use hash table to solve it. Here's a better solution using bucket sort.

Code in Python:

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