leetcode

简单数组哈希表滑动窗口

方法1 暴力解法

var containsNearbyDuplicate = function(nums, k) {
  const len = nums.length;
  for(let i = 0; i < len; i++) {
    const item = nums[i];
    for(let j = i + 1; j < len; j++) {
      if (item === nums[j] && j - i <= k) return true;
    }
  }
  return false;
};

方法2 哈希表

var containsNearbyDuplicate = function(nums, k) {
  const map = new Map();
  for(let i = 0; i < nums.length; i++) {
    const item = nums[i];
    if (map.has(item) && i - map.get(item) <= k) return true;
    map.set(item, i);
  }
  return false;
};

核心逻辑：一旦出现重复项，只要从前边扫过的项中找与自身距离最近的重复项进行比较，判断两者之间的距离是否满足要求即可。

如果出现重复的 key，也就是出现了重复的成员。
并且此时出现的这个重复的成员不满足条件，那么直接使用该成员覆盖 map 中原有的成员即可。
这么做是合理的，因为与下一个重复成员更近的是当前出现的这个重复成员，下面举例说明
nums： [1, 2, 3, 1, 4, 1]
k：2

{
  "1": 0,
  "2": 1,
  "3": 2,
}

方法3 滑动窗口

var containsNearbyDuplicate = function (nums, k) {
  const set = new Set();
  for (let i = 0; i < nums.length; i++) {
    const item = nums[i];
    if (i >= k + 1) set.delete(nums[i - k - 1]); // 收缩窗口
    if (set.has(item)) return true;
    set.add(item); // 扩展窗口
  }
  return false;
};

⚠️ 顺序

1. 收缩窗口
2. 判断重复成员
3. 扩展窗口