219. 存在重复元素 II

;(function () {
  /**
   * 219. 存在重复元素 II
   * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j , 满足 nums[i] == nums[j] 且 abs(i - j) <= k
   * 如果存在，返回 true ；否则，返回 false 。
   *
   * 输入：nums = [1,2,3,1], k = 3
   * 输出：true
   *
   * 输入：nums = [1,0,1,1], k = 1
   * 输出：true
   *
   * 输入：nums = [1,2,3,1,2,3], k = 2
   * 输出：false
   *
   */

  function containsNearbyDuplicate(nums: number[], k: number): boolean {
    // 方法一： ---------- 数据量很大的情况下，运行时间太长 ----------------------
    // let len = nums.length;
    // let p1 = 0;
    // for (let i = 0; i < len; i++) {
    //     let cur = nums[i]
    //     p1 = i + 1;
    //     while (p1 < len) {
    //         if (cur === nums[p1] && p1 - i <= k) {
    //             // console.log('Get:' + cur, p1)
    //            return true
    //         }
    //         p1++
    //     }
    // }
    // return false

    // 方法二：哈希
    // const map = new Map();
    // const len = nums.length;
    // for (let i = 0; i < len; i++) {
    //     const cur = nums[i]
    //     if (map.has(cur) && i - map.get(cur) <= k) {
    //         return true
    //     }
    //     map.set(cur, i)
    // }
    // return false

    // 方法三： 滑动窗口（很切题啊）
    const set = new Set()
    const len = nums.length
    for (let i = 0; i < len; i++) {
      if (i > k) {
        set.delete(nums[i - k - 1])
      }
      if (set.has(nums[i])) {
        return true
      }
      set.add(nums[i])
    }
    return false
  }

  // console.log(containsNearbyDuplicate([1, 2, 3, 1], 3))
  console.log(containsNearbyDuplicate([1, 0, 1, 1], 2))
  // console.log(containsNearbyDuplicate([1,2,3,1,2,3], 2))
})()