leetcode-220 存在重复元素 III

题目:

检测一个包含整数的数组中是否存在nums[j],nums[i],
使得nums[i]-nums[j]的绝对值不超过t，并且i和j的距离不超过k。
例子：
Input：nums = [1,2,3,1], k=3, t=0
Output: true

这道题使用桶排序，虽然桶排序占据的空间较大，但速度更快。先把题目要求翻译成不等式会更方便写出代码：
设数组中任意两个满足题目要求的整数为v1，v2，假设v1是已知的，v2是要寻找的满足条件的整数。
|v1-v2|<=t
-t <= v1-v2 <= t
-1 <= v1/t - v2/t <= 1
v1/t-1 <= v2/t <= v1/t+1
由此，我们就有了在桶中寻找符合条件的v2的范围。
代码如下：

#python3
class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        bucket = {}
        for i,v in enumerate(nums):
            bucketindex, offset = (v//t, 1) if t else (v, 0)
            for idex in range(bucketindex - offset, bucketindex + offset + 1):
                if idex in bucket and abs(bucket[idex]-nums[i]) <= t: #由于//取整后，范围并不是推导出来的严格的范围，所以在范围内之后还要确定是否满足差为t
                    return True
            bucket[bucketindex] = nums[i]
            if len(bucket) > k:
                del bucket[nums[i-k]//t if t else nums[i-k]] #相当于以k为周期向数组尾部移动，因此需要每次删掉周期内第一个元素
        return False

这个方法十分巧妙，由于t>=0，所以bucket内并不会有重复的元素，因为只要重复元素出现的间隔在k以内，都会在第二个for循环内部被返回true。