220.存在重复元素III

链接：220.存在重复元素III
难度：Hard
标签：数组、桶排序、有序集合、排序、滑动窗口
简介：给你一个整数数组 nums 和两个整数  k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得  abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。如果存在则返回 true，不存在返回 false。

题解 1 - typescript

• 编辑时间：2021-08-15
• 执行用时：864ms
• 内存消耗：46.3MB
• 编程语言：typescript
• 解法介绍：针对每次窗口进行二分排序。

class SortSet {
  set = new Set<number>();
  initSuccess = true;
  constructor(public arr: number[], public k: number) {
    arr.sort((a, b) => a - b);
    if (this.check()) {
      this.initSuccess = false;
      return;
    }
    for (const num of arr) {
      if (this.set.has(num)) {
        this.initSuccess = false;
        break;
      }
      this.set.add(num);
    }
  }
  add(num: number): boolean {
    if (this.set.has(num)) return false;
    let l = 0;
    let r = this.arr.length - 1;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (this.arr[mid] >= num) r = mid;
      else l = mid + 1;
    }
    this.arr.splice(this.arr[l] < num ? this.arr.length : l, 0, num);
    this.set.add(num);
    return true;
  }
  del(num: number): void {
    let l = 0;
    let r = this.arr.length - 1;
    let mid!: number;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (this.arr[mid] > num) r = mid - 1;
      else if (this.arr[mid] < num) l = mid + 1;
      else break;
    }
    this.arr.splice(mid, 1);
    this.set.delete(num);
  }
  check(): boolean {
    for (let i = 0; i < this.arr.length - 1; i++) {
      if (this.arr[i + 1] - this.arr[i] <= this.k) return true;
    }
    return false;
  }
}
function containsNearbyAlmostDuplicate(nums: number[], k: number, t: number): boolean {
  const n = nums.length;
  const set = new SortSet(nums.slice(0, k + 1), t);
  if (!set.initSuccess) return true;
  for (let i = k + 1; i < n; i++) {
    set.del(nums[i - k - 1]);
    if (!set.add(nums[i])) return true;
    if (set.check()) return true;
  }
  return false;
}

题解 2 - typescript

• 编辑时间：2021-04-17
• 执行用时：176ms
• 内存消耗：56.9MB
• 编程语言：typescript
• 解法介绍：利用 map 储存后排序计算。

function containsNearbyAlmostDuplicate(nums: number[], k: number, t: number): boolean {
  if (k === 0) return false;
  const map = new Map<number, number[]>();
  for (let i = 0, len = nums.length; i < len; i++) {
    const num = nums[i];
    let arr = map.get(num);
    if (!arr) map.set(num, (arr = []));
    arr.push(i);
  }
  const data = [...map.entries()].sort(([num1], [num2]) => num1 - num2);
  const check = (arr1: number[], arr2: number[]) =>
    (arr1[arr1.length] < arr2[0] && Math.abs(arr1[arr1.length] - arr2[0]) <= k) ||
    (arr2[arr2.length] < arr1[0] && Math.abs(arr2[arr2.length] - arr1[0]) <= k) ||
    arr1.some(i1 => arr2.some(i2 => Math.abs(i1 - i2) <= k));
  for (let i = 0, l = data.length; i < l; i++) {
    const arr1 = data[i][1];
    if (arr1.some((v, i, arr) => (i === 0 ? false : v - arr[i - 1] <= k))) return true;
    let index = i - 1;
    while (index >= 0 && data[i][0] - data[index][0] <= t)
      if (check(arr1, data[index--][1])) return true;
  }
  return false;
}