219. Contains Duplicate II【easy】

时间:2022-02-21 06:51:30

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;
}
};

219. Contains Duplicate II【easy】

解法一:

 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.