LeetCode笔记：存在重复元素 II
问题
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
示例 1:
输入: nums = [1,2,3,1], k= 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k=1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k=2
输出: false
解法一
思路：
用一个对象来存储每个数字的信息，利用 key 不能重复的原理，每次遇到新的重复的数字，就更新位置信息和最近一个重复数字的绝对值，一旦遇到一个绝对值比k小就是成功找到了想要的数字。
代码：
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function (nums, k) {
// 初始化存储空间
const obj = {};
// 一遍循环即可，遍历所有的数字
for (let i = 0; i < nums.length; i++) {
// 当前数字
const n = nums[i];
// 是否出现重复数字
if (n in obj) {
// 重复出现的数字，绝对值需要更新为和前一个值的差，因为和前一个的差肯定更小
obj[n].abs = i - obj[n].i;
// 上面计算完差值，就可以更新当前位置了，用于下一次重复出现的时候计算差值
obj[n].i = i;
// 一旦发现当前差值小于k，即满足条件退出
if (obj[n].abs <= k) return true;
} else {
// 第一次出现的数字进行初始化，存储位置和绝对值（因为第一次出现，所以绝对值为0）
obj[n] = {
i: i,
abs: 0,
};
}
}
//如果上面的循环中没有找到满足条件的数字，默认返回`false`
return false;
};
解法二
思路：
利用Set不允许重复元素的特性，做一个k大小的滑动窗口，一直往前滑动寻找窗口内是否出现相同元素。这个滑动窗口需要的空间更小。
代码：
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function (nums, k) {
const set = new Set();
for (let i = 0; i < nums.length; i++) {
// 滑动窗口内一旦出现重复元素，即满足要求
if (set.has(nums[i])) {
return true;
}
// 每个值都加入
set.add(nums[i]);
// 一旦数量超出k，就删除第一个数字，即滑动窗口右移
if (set.size > k) {
set.delete(nums[i - k]);
}
}
return false;
};
评论