在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。 如果存在则返回 true，不存在返回 false。
输入: nums = [1,5,9,1,5,9], k = 2, t = 3 输出: false分析：与(219)存在重复元素 II不同在于在k窗口基础上，将相等改为绝对值。 ==> 哈希表 + 桶排序：
""" 用哈希表模拟桶,hash[num] = i ，即num 在第i桶内; 桶排序将不同的num放入不同的桶中：nbucket = num//(t+1)，这样在一个桶中有t+1个数,绝对值只差最多为t eg. bucket_0[num = 0,...,t],bucket_1[num = t+1,...,2t+1] ⇒ 如果两个数在一个桶内则两个数绝对差值一定<=t，中; 相邻桶差值最多为(2t+1 - 0)=2t+1，最小为(t+1 -t)=1 所以相邻桶要算一下； 不相邻桶元素绝对值差一定>t ,下一轮; """ class Solution: def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool: # bucket sort if t<0 or k <0: return False bucketDict = {} for i,num in enumerate(nums): nbucket = num//(t+1) if nbucket in bucketDict: return True if nbucket-1 in bucketDict: if abs(num-bucketDict[nbucket-1])<=t: return True if nbucket+1 in bucketDict: if abs(num-bucketDict[nbucket+1])<=t: return True bucketDict[nbucket] = num # 维护窗口 # [0,...,i-k,..., i,...] # |k+1个数| if len(bucketDict)>k: bucketDict.pop(nums[i-k]//(t+1)) return False