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 absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1 Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2 Output: false
本题是LeetCode Contains Duplicate的升级版，要求是判断是否有距离不超过k的两个相同的数。
首先想到暴力方法，一种是直接两层长度为n的循环，判断是否有距离不超过k的两个相等的数，另一种是外层循环为n，内层只要循环长度k，因为即使超过k有相等数的，也不符合题意。尝试之后显然超时。
然后我想到了另一种方法，把数组中所有相同数字的下标都放到一个桶里，后续再在这个桶里看是否有距离不超过k的两个下标对；如果桶里只有一个下标，说明这个下标对应的数没有重复出现，直接continue。完整代码如下：
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;
}
};本代码提交AC，用时46MS。
后来看欣欣的解法LeetCode Contains Duplicate II，发现这个解法好厉害啊，用到了高级的unordered_set，之前只用过unordered_map，赶紧来学习一下。
她的思路是这样的，题目要求相同元素的距离不超过k，则我们维护一个长度为k的滑动窗口，把这个窗口里的所有数都hash到unordered_set里，后续每来一个元素，去这个hash_set里查之前是否出现过，因为我们的hash_set里只保留了前k个元素，所以如果hash_set查到了，他们的距离肯定是不超过k的。这种解法真是漂亮！完整代码如下：
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;
}
};本代码提交AC，用时29MS，果然比我的速度快，厉害~
二刷。用一个hash表记录每个数最近出现的下标，如果新来一个数，之前在hash表中出现过，则看看下标之差是否小于等于k，是则返回true；否则更新hash。
思路非常简单，代码如下：
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;
}
};本代码提交AC，用时35MS。
