给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。如果存在则返回 true，不存在返回 false。

桶排序 + 滑动窗口

按照元素的大小进行分桶，维护一个滑动窗口内的元素对应的元素。

对于元素 x，其影响的区间为 [x - t, x + t]。于是我们可以设定桶的大小为 t + 1。如果两个元素同属一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 t。如果两个元素既不属于同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。

因为一个桶内至多只会有一个元素，用hash实现

• 时间复杂度O(n)，空间复杂度O(min(n, k))
• Runtime: 123 ms, faster than 86.14%
• Memory Usage: 45.5 MB, less than 9.36%

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, k, t) {
  const len = nums.length;
  const map = new Map();
  for (let i = 0; i < len; i++) {
    const val = nums[i];
    const idx = getIdx(val, t + 1);
    if (map.has(idx)) {
      return true;
    }
    if (map.has(idx - 1) && Math.abs(map.get(idx - 1) - val) <= t) {
      return true;
    }
    if (map.has(idx + 1) && Math.abs(map.get(idx + 1) - val) <= t) {
      return true;
    }
    map.set(idx, val);
    if (i >= k) {
      map.delete(getIdx(nums[i - k],  t + 1));
    }
  }
  return false;
};

var getIdx = function(val, width) {
  return val < 0 ? Math.floor((val + 1) / width) - 1 : Math.floor(val / width);
}