- Leetcode 217. Contains Duplicate
- Leetcode 219. Contains Duplicate II
- Leetcode 220. Contains Duplicate III
Leetcode Contain Duplicates Series
Leetcode 217. Contains Duplicate
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
The idea: set doesn’t allow the number duplicate input
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
return nums.size() > unordered_set<int>(nums.begin(), nums.end()).size();
}
};
Leetcode 219. Contains Duplicate II
The idea: use the map to store the nums[i] index
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> map;
for (int i=0; i<nums.size(); i++) {
if (map[nums[i]]) {
if (i+1-map[nums[i]] <= k)
return true;
}
map[nums[i]] = i+1;
}
return false;
}
};
Leetcode 220. Contains Duplicate III
Leetcode 220. Contains Duplicate III
The idea: use the map
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (nums.empty()) return false;
map<int, int> m;
int j = 0;
for (int i=0; i<nums.size(); i++) {
if (i-j >k && m[nums[j]]==j)
m.erase(nums[j++]);
auto a = m.lower_bound(nums[i]-t);
if (a!=m.end() && abs(a->first - nums[i])<=t)
return true;
m[nums[i]] = i;
}
return false;
}
};
近期评论