# 存在重复元素II（219）
# 题目
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
# 示例
输入: 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
# 算法
# 滑动窗口
维护一个长度为k的滑动窗口，在里面寻找是否有相同元素
使用双层for循环或者双指针
export const containsNearbyDuplicate = (nums, k) => {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length && j <= i + k; j++) {
if (nums[i] === nums[j]) {
return true;
}
}
}
return false;
};
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
export const containsNearbyDuplicate = (nums, k) => {
if (k === 0) return false;
let l = 0,
r = 1;
while (l < nums.length - 1) {
if (nums[l] === nums[r]) {
return true;
}
if (l + k > r && r < nums.length) { // 当右指针大于数组长度时，应该跳过
r++;
} else {
l++;
r = l + 1;
}
}
return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 哈希表
创建一个长度为k的数组，遍历nums，有相同元素则返回true，否则每推入一个元素则弹出第一个元素
export const containsNearbyDuplicate = (nums, k) => {
let set = [];
for (let i = 0; i < nums.length; i++) {
if (set.indexOf(nums[i]) > -1) {
return true;
}
set.push(nums[i]);
if (set.length > k) {
set.shift();
}
}
return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
使用set数据结构实现哈希表
export const containsNearbyDuplicate = (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]);
if (set.length > k) {
set.delete(nums[i - k]);
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12