https://leetcode-cn.com/problems/contains-duplicate-ii/
题目
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
示例
1
2
| 输入: nums = [1,2,3,1], k = 3
输出: true
|
解一：Map哈希表
思路
维护一个哈希表存储 【值：索引】对
初始化将nums[0]加入
扫描数组
- 如果扫描到在哈希表中的数据，判断是否距离超过k
- 没超过，返回true
- 超过，更新键值对的索引值
- 如果扫描到不在哈希表中的数据，将它加入
返回false
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| /**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function(nums, k) {
//哈希法
let map=new Map();
map.set(nums[0],0)
for (let i=1;i<nums.length;i++){
//如果不在map中,加入
if (map.get(nums[i])!==undefined){
if (i-map.get(nums[i])<=k) return true;
}
map.set(nums[i],i)
}
return false
};
|
解二：Set类滑动窗口，算哈希吧
思路
维护一个哈希表，里面至多包含k个元素
出现重复值时返回true
如果哈希表中存在大于k个元素，移除最前面的数
代码
1
2
3
4
5
6
7
8
9
10
11
| var containsNearbyDuplicate = function(nums, k) {
//哈希法
let set=new Set();
for (let i=0;i<nums.length;i++){
//如果不在set中,加入
if (set.has(nums[i])) return true;
set.add(nums[i])
if(set.size>k) set.delete(nums[i-k])
}
return false
};
|