68 lines
1.9 KiB
JavaScript
68 lines
1.9 KiB
JavaScript
/**
|
||
* https://leetcode.cn/problems/contains-duplicate-ii/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {number[]} nums
|
||
* @param {number} k
|
||
* @return {boolean}
|
||
*/
|
||
const containsNearbyDuplicate = function (nums, k) {
|
||
|
||
};
|
||
|
||
/*
|
||
定义两个指针表示abs(i - j) <= k的窗口，i向右移动，查看当前指向的值在set中是否存在，不存在就把这个值存入set，如果i-j >k 表明
|
||
当前太大了，要缩小，把j指向的元素从set中剔除掉，i++,并将测j指向的值是否在set中存在
|
||
*/
|
||
function f1(nums, k) {
|
||
const set = new Set();
|
||
|
||
for (let i = 0, j = 0; i < nums.length; i++) {
|
||
// 如果 窗口太大，就缩小窗口再检测
|
||
if (i - j > k) {
|
||
set.delete(nums[j]);
|
||
j++;
|
||
}
|
||
|
||
// 检测 nums[i]是否在set中存在
|
||
if (set.has(nums[i])) return true;
|
||
|
||
// 将当前值存入set
|
||
set.add(nums[j]);
|
||
}
|
||
return false;
|
||
}
|
||
|
||
/*
|
||
优化，上面代码中i-j<k的检测是多余的，因为，当i>k时i-j一定大于k,因为后续我们会一个值一个值的检测，例如：当k=3,i=4时，这个时候
|
||
一定要缩小串口，直接剔除掉i-k-1表示的元素即可，set中剩下的元素还是4个，这样可以少用一个下标，判断也更快
|
||
*/
|
||
function f2(nums, k) {
|
||
const set = new Set();
|
||
|
||
for (let i = 0; i < nums.length; i++) {
|
||
// 超出滑动窗口
|
||
if (i > k) {
|
||
set.delete(nums[i - k - 1]);
|
||
}
|
||
// 检测set中是否含有这个元素
|
||
if (set.has(nums[i])) return true;
|
||
set.add(nums[i]);
|
||
}
|
||
return false;
|
||
}
|
||
|
||
/*
|
||
直接一次遍历，利用map储存之前遍历的所有值和下标，如果当前值在map中存在，并且当前值的下标减去map中对应值的小标，结果小于等于k
|
||
则表明发生了重复
|
||
*/
|
||
|
||
function f3(nums, k) {
|
||
const map = new Map();
|
||
|
||
for (let i = 0; i < nums.length; i++) {
|
||
const num = nums[i];
|
||
if (map.has(num) && i - map.get(num) <= k) return true;
|
||
map.set(num, i);
|
||
}
|
||
return false;
|
||
}
|