Description:
https://leetcode.com/problems/contains-duplicate-ii/#/description
Algorithm:
Easy
Code:
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if (nums.size() < 2) return false;
unordered_map <int, int> record;
for (int i = 0; i < nums.size();i++)
{
if (record.find(nums[i]) != record.end() && i - record[nums[i]] <= k)
return true;
else
record[nums[i]] = i;
}
return false;
}
};
Time & Space:
O(nlogn) & O(n)
map底层是红黑树实现的，因此它的find函数时间复杂度：O(logn)