桶排序

220. 存在重复元素 III

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        bucket = dict()
        if t < 0: return False
        for i in range(len(nums)):
            nth = nums[i] // (t + 1)
            if nth in bucket:
                return True
            if nth - 1 in bucket and abs(nums[i] - bucket[nth - 1]) <= t:
                return True
            if nth + 1 in bucket and abs(nums[i] - bucket[nth + 1]) <= t:
                return True
            bucket[nth] = nums[i]
            if i >= k: bucket.pop(nums[i - k] // (t + 1))
        return False

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        from sortedcontainers import SortedSet
        st = SortedSet()
        left, right = 0, 0  
        res = 0
        while right < len(nums):
            if right - left > k:   # 移动窗口
                st.remove(nums[left])
                left += 1
            #  在st中查找nums[right] - t，存在时返回nums[right] - t左侧的位置，不存在返回应该插入的位置.
            index = bisect.bisect_left(st, nums[right] - t)  
            print(st)
            if st and index >= 0 and index < len(st) and abs(st[index] - nums[right]) <= t:
                return True
            st.add(nums[right])
            right += 1
        return False