存在重复元素-iii

Tips

题目

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

示例

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

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

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

题解

JavaScript - 朴素滑动窗口
JavaScript - 桶排序

相当于在确保小于等于 indexDiff 的窗口下, 存不存在一组 nums[i] 和 nums[j] 绝对值小于等于 valueDiff, 但这个方法会超时.

/**
 * @param {number[]} nums
 * @param {number} indexDiff
 * @param {number} valueDiff
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function (nums, indexDiff, valueDiff) {
  const n = nums.length

  for (let i = 0; i < n; i++) {
    const maxJ = i + indexDiff
    let j = maxJ >= n ? n - 1 : maxJ

    while (i < j) {
      if (Math.abs(nums[i] - nums[j]) <= valueDiff) {
        return true
      }

      j--
    }
  }

  return false
}

我们也可以使用利用桶排序的思想解决本题. 按照元素的大小进行分桶, 维护一个滑动窗口内的元素对应的元素.

对于元素 x, 其影响的区间为 [x − t, x + t]. 于是我们可以设定桶的大小为 t + 1.

如果两个元素同属一个桶, 那么这两个元素必然符合条件.
如果两个元素属于相邻桶, 那么我们需要校验这两个元素是否差值不超过 t.
如果两个元素既不属于同一个桶, 也不属于相邻桶, 那么这两个元素必然不符合条件.

计算桶大小: 桶大小 size = valueDiff + 1.
创建哈希表: 使用一个哈希表 bucketMap 来存储每个桶的代表元素.
遍历数组: 遍历输入的数组 nums, 对于每个元素 nums[i]:
- 计算桶索引: 计算当前元素 nums[i] 应该放入哪个桶, bucketIndex = nums[i] / size.
- 检查相邻桶: 检查当前桶, 左边相邻的桶和右边相邻的桶中是否存在满足条件的元素.
- 更新哈希表: 将当前元素 nums[i] 放入对应的桶中.
返回结果: 如果遍历完整个数组, 没有发现满足条件的元素, 则返回 false.

/**
 * @param {number[]} nums
 * @param {number} indexDiff
 * @param {number} valueDiff
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function (nums, indexDiff, valueDiff) {
  const bucketMap = new Map()
  const size = valueDiff + 1

  var getId = function (num) {
    return Math.floor(num / size)
  }

  for (let i = 0; i < nums.length; i++) {
    const id = getId(nums[i])

    // 检查当前桶
    if (bucketMap.has(id)) {
      return true
    }

    // 检查左边相邻的桶
    if (
      bucketMap.has(id - 1) &&
      Math.abs(nums[i] - bucketMap.get(id - 1)) <= valueDiff
    ) {
      return true
    }

    // 检查右边相邻的桶
    if (
      bucketMap.has(id + 1) &&
      Math.abs(nums[i] - bucketMap.get(id + 1)) <= valueDiff
    ) {
      return true
    }

    // 更新哈希表
    bucketMap.set(id, nums[i])

    // 移除超出窗口范围的桶
    if (i >= indexDiff) {
      bucketMap.delete(getId(nums[i - indexDiff]))
    }
  }

  return false
}

时间复杂度: O(n), 其中 n 是给定数组的长度. 每个元素至多被插入哈希表和从哈希表中删除一次, 每次操作的时间复杂度均为 O(1).
空间复杂度: O(min(n, k)), 其中 n 是给定数组的长度. 哈希表中至多包含 min(n, k + 1).

题目​

题解​

题目

题解