存在重复元素 III

题目

题目来源：力扣（LeetCode）

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

如果存在则返回 true，不存在返回 false。

示例 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

思路分析

1. 我们按照元素的大小进行分桶，维护一个滑动窗口内的元素对应的元素。
2. 对于元素 x，其影响的区间为 [x - t, x + t]。于是我们可以设定桶的大小为 t + 1。如果两个元素同属一 个桶，那么这两个元素必然符合条件。
3. 如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 t。如果两个元素既不属于 同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。

具体的做法为：令桶的大小为 size = t + 1，根据当前遍历到的元素 x 计算所在桶编号：

• 如果已经存在该桶，说明前面已有 [x - t, x + t] 范围的数字，返回 true
• 如果不存在该桶，则检查相邻两个桶的元素是有 [x - t, x + t] 范围的数字，如有 返回 true
• 建立目标桶，并删除下标范围不在 [max(0, i - k), i) 内的桶

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function (nums, k, t) {
  // 获取桶的编号
  function getId(x) {
    // 令桶的大小为 t + 1 ，是为了确保差值小于等于 t 的数能够落到一个桶中
    return Math.floor(x / (t + 1));
  }
  if (t < 0) return false;
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    // 当前元素所属于的桶的编号
    const id = getId(nums[i]);
    // 当前元素所属于的桶中已经有元素，此时桶中的元素和当前元素的绝对值一定小于等于 t
    if (map.has(id)) {
      return true;
    } 
    // 看看当前桶和后面相邻桶有没有符合条件
    else if (map.has(id + 1) && Math.abs(map.get(id + 1) - nums[i]) <= t) {
      return true;
    } 
    // 看看当前桶和前面相邻桶有没有符合条件的
    else if (map.has(id - 1) && Math.abs(map.get(id - 1) - nums[i]) <= t) {
      return true;
    }
    // 建立目标桶，将当前元素放入其属于的桶中
    map.set(id, nums[i]);
    // 移除下标范围不在 [max(0, i - k), i) 内的桶
    if (i >= k) {
      map.delete(getId(nums[i - k]));
    }
  }
  return false;
};