1.题目描述
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。 示例 1: 示例 2: 示例 3:
2.思路（散列表）
遍历数组，对于每个元素做以下操作： 1.在散列表中搜索当前元素，如果找到了就返回 true。 2.在散列表中插入当前元素。 3.如果当前散列表的大小超过了 k， 删除散列表中最旧的元素。 否则返回false。
3.代码
class Solution {
public:
bool containsNearbyDuplicate(vector
<int>& nums
, int k
) {
set
<int> hash_set
;
for(int i
= 0; i
< nums
.size(); ++i
){
if(hash_set
.count(nums
[i
])){
return true;
}
hash_set
.insert(nums
[i
]);
if(hash_set
.size() > k
){
hash_set
.erase(nums
[i
- k
]);
}
}
return false;
}
};
4.复杂度分析
时间复杂度：O(n) 空间复杂度：O(n)
Processed:
0.019, SQL:
10
