Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Analyze

思路: 参照官方题解该题可以使用桶排序的思想来设置查找表的 key - value。比较好理解的一个例子: 小敏生日在 3 月份, 她想知道是否有其他同学生日和她在 30 天以内, 假设每个月有 30 天, 那么只要找 2 月份和 4 月份两个月生日的同学就行了, 转化到该题目即 key 只要保留一个 value 就行。

桶排序的思想: 将数据根据归类划分到若干个区域, 然后对该些区域分别进行排序;

此题综合了滑动窗口、查找表、桶排序的知识, 需要二刷。

| i - j | ≤ k
| nums[i] - nums[j] | ≤ t

• 此外需要考虑边界值
  • k <= 0、 t <= 0

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, k, t) {
  if (k < 0 || t < 0) return false
  const getKey = (value) => {
    return Math.floor(value / (t + 1))
  }

  const map = new Map()

  let l = 0
  while (l < nums.length) {
    const key = getKey(nums[l])

    if (map.has(key)) {
      return true
    } else if (map.has(key + 1) || map.has(key - 1)) {
      if (map.get(key + 1) - nums[l] <= t) { return true }
      if (nums[l] - map.get(key - 1) <= t) { return true }
    }

    map.set(key, nums[l])

    if (l >= k) {
      map.delete(getKey(nums[l - k]))
    }

    l++
  }

  return false
}

Sister Title

217、219