219. Contains Duplicate II【easy】
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.
错误解法:
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if (nums.empty()) {
return false;
} unordered_map<int, int> my_map;
for (int i = ; i < nums.size(); ++i) { if (my_map.find(nums[i]) == my_map.end()) {
my_map[nums[i]] = i;
}
else {
if (abs(i - my_map[nums[i]]) <= k) {
return true;
}
}
} return false;
}
};
解法一:
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if (nums.empty()) {
return false;
} unordered_map<int, int> my_map;
for (int i = ; i < nums.size(); ++i) {
if (my_map.find(nums[i]) != my_map.end() && abs(i - my_map[nums[i]]) <= k) {
return true;
}
my_map[nums[i]] = i;
} return false;
}
};
参考@jianchao.li.fighter 的代码
Well, the basic idea is fairly straightforward. We maintain a mapping mp
from a value in nums
to its position (index) i
. Each time we meet an unseen value, we add it to the map (mp[nums[i]] = i
). Otherwise, depending on whether the recorded index mp[nums[i]]
and the current index i
satisfy i - mp[nums[i]] <= k
(node that the new index i
is larger than the old index mp[nums[i]]
), we return true
or update the index (mp[nums[i]] = i
). If all the elements have been visited and we have not returned true
, we will return false
.
解法二:
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_set<int> s; if (k <= ) return false;
if (k >= nums.size()) k = nums.size() - ; for (int i = ; i < nums.size(); i++)
{
if (i > k) s.erase(nums[i - k - ]);
if (s.find(nums[i]) != s.end()) return true;
s.insert(nums[i]);
} return false;
}
};
参考@luo_seu 的代码,就是维持固定那么多长度的数值
The basic idea is to maintain a set s which contain unique values from nums[i - k] to nums[i - 1],
if nums[i] is in set s then return true else update the set.