Title
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.
at most是之多的意思嘛
判断是否冗余，这个冗余是相邻索引差小于等于K的
Solution
首先想到了hash表嘛
第一次写的ac
不是最优的，用undered_set做的，但做的代码太多了，zz,第一次写的
//cpp:
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> uset;
if (nums.size() > k) {
for (int i = 0; i < k+1; i++) {
if (uset.find(nums[i]) == uset.end())
uset.insert(nums[i]);
else
return true;
}
for (int i = k+1; i < nums.size(); i++) {
uset.erase(nums[i - k - 1]);
if (uset.find(nums[i]) == uset.end())
uset.insert(nums[i]);
else
return true;
}
}
else {
for (int i = 0; i < nums.size(); i++) {
if (uset.find(nums[i]) == uset.end())
uset.insert(nums[i]);
else
return true;
}
}
return false;
}
};
unordered_set优化
对第一次的代码优化
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_set<int> s;
if (k <= 0) return false;
if (k >= nums.size()) k = nums.size() - 1;
for (int i = 0; i < nums.size(); i++)
{
if (i > k) s.erase(nums[i - k - 1]);
if (s.find(nums[i]) != s.end()) return true;
s.insert(nums[i]);
}
return false;
}
};
hashmap
其实这种最好用hashmap,一旦出现啥要求的话，比如索引呀
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> nmap;
for (int i = 0; i <nums.size();i++)
{
if (nmap.count(nums[i]) == 0)
nmap[nums[i]] = i;
else if (i - nmap[nums[i]] <=k)
return true;
else
nmap[nums[i]] = i;
}
return false;
}