# LeetCode Contains Duplicate II

LeetCode Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j]and the difference between i and j is at most k.

```class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if (nums.size() == 0)return false;
unordered_map<int, int> hash_table;
int distinct_cnt = 1; // 相异元素的个数
vector<vector<int>> duplicate_indices = { {} }; // 跳过第0个桶
for (int i = 0; i < nums.size(); i++) {
if (hash_table[nums[i]] == 0) {
hash_table[nums[i]] = distinct_cnt++;
duplicate_indices.push_back({ i });
}
else {
duplicate_indices[hash_table[nums[i]]].push_back(i); // 把相同元素的下标都放到一个桶里
}
}
for (int i = 1; i < duplicate_indices.size(); i++) { // 查每个桶
if (duplicate_indices[i].size() < 2)continue;
for (int u = 0; u < duplicate_indices[i].size() - 1; u++) {
for (int v = u + 1; v < duplicate_indices[i].size(); v++) {
if (duplicate_indices[i][v] - duplicate_indices[i][u] <= k)return true;
}
}
}
return false;
}
};
```

```class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if (nums.size() == 0 || k <= 0)return false;
if (k >= nums.size())k = nums.size() - 1;
unordered_set<int> hash_set;
for (int i = 0; i < nums.size(); i++) {
if (i > k)hash_set.erase(nums[i - k - 1]); // 滑动窗口，删掉窗口第一个元素
if (hash_set.find(nums[i]) != hash_set.end())return true;
hash_set.insert(nums[i]); // 把新元素插入窗口
}
return false;
}
};
```

```class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> hash;
for(int i = 0; i < nums.size(); ++i) {
if(hash.find(nums[i]) != hash.end() && i - hash[nums[i]] <= k) return true;
hash[nums[i]] = i;
}
return false;
}
};
```