https://leetcode.com/problems/contains-duplicate-iii/
桶排序的思想，很少碰到，但是的确很精妙。

个人解答

  1. class Solution:
  2.     def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
  3.         bucket = {} # numbers in same bucket, have difference <= t
  4.         bucketSize = t + 1
  5.         for i, x in enumerate(nums):
  6.             idx = x // bucketSize
  7.             # check three possible condition, current bucket and neighbor buckets
  8.             if idx in bucket:
  9.                 return True
  10.             if idx - 1 in bucket and abs(bucket[idx - 1] - nums[i]) <= t:
  11.                 return True
  12.             if idx + 1 in bucket and abs(bucket[idx + 1] - nums[i]) <= t:
  13.                 return True
  14.             bucket[idx] = x
  16.             # remove out bound value
  17.             if i - k >= 0:
  18.                 del(bucket[nums[i - k] // bucketSize])
  19.         return False

题目分析

之前的contain duplicate问题，由于idx范围的限制，很容易想到要用sliding window，这道题也有这样的设定，但是对于如何判断duplicate，本题并不能直接相等判断。

所以，本题关键是如何快速判断当前窗口中的所有值，是否有与之相距<=t的，而这就要用到桶排序的思想，每t+1搁长度的区间构成一个桶，如此，有两种情况两个值相距可能<=t：

  1. 两数在同一个桶之中
  2. 两数在相邻桶之中

这样，最多只要判断三个数就可以完成！

维护这样的桶也比较容易，每次窗口前进一步的时候，就把之前的桶里对应的值删掉。