220. 存在重复元素 III.md

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1:

输入: nums = [1,2,3,1], k = 3, t = 0
输出: true

示例 2:

输入: nums = [1,0,1,1], k = 1, t = 2
输出: true

示例 3:

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

思路： 利用桶排序的思路，把桶作为窗口，只需要比较当前桶，前一个/后一个桶即可

solution:

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, k, t) {
    // 解决js中 -0 === 0 为true的问题
    function getId(x, w) {
        return Math.floor(x / w)
    }
    if (t < 0) return false
    const map = new Map()
    const w = t + 1
    for (let i = 0; i < nums.length; i++) {
        const m = getId(nums[i] ,w)
        if (map.has(m)) return true
        else if (map.has(+m + 1) && Math.abs(map.get(+m + 1) - nums[i]) < w) return true
        else if (map.has(+m - 1) && Math.abs(map.get(+m - 1) - nums[i]) < w) return true
        map.set(m, nums[i])
        if (i >= k) map.delete(getId(nums[i - k], w))
    }
    return false
};