题目来源
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.
第一想法就是把每种情况都列一下，复杂度O(kn)。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
for (int i=0; i<n-1; i++)
for (int j=i+1; j<=i+k && j<n; j++)
if (nums[i] == nums[j])
return true;
return false;
}
};
不出意外TLE了。
然后又想了想，用哈希，记录下每个数字出现的位置。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, vector<int>> map;
int n = nums.size();
for (int i=0; i<n; i++) {
if (map.find(nums[i])!=map.end() && (i - map[nums[i]].back() <= k))
return true;
map[nums[i]].push_back(i);
}
return false;
}
};
看了看答案，发现只要记录k个就可以了，里面有重复的就true。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> s;
int n = nums.size();
for (int i=0; i<n; 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;
}
};
