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

滑动窗口 排序 中等 每日一题 👆桶排序

👇维护一个大小k的有序组

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
            index = bisect.bisect_left(st, nums[right] - t)
            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