Leetcode 219.Contains duplicate II 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(n)
// 空间复杂度: O(k)
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if( nums.size() <= 1 )
return false;
if( k <= 0 )
return false;
unordered_set<int> record;
for( int i = 0 ; i < nums.size() ; i ++ ){
if( record.find( nums[i] ) != record.end() )
return true;
record.insert( nums[i] );
// 保持record中最多有k个元素
// 因为在下一次循环中会添加一个新元素,使得总共考虑k+1个元素
if( record.size() == k + 1 )
record.erase( nums[i-k] );
}
return false;
}
};
bool containsNearbyDuplicate(vector<int>& nums, int k) {
set<int> cand;
for (int i = 0; i < nums.size(); i++) {
//k+1 [0,k] K+1-K-1=0
if (i > k) cand.erase(nums[i-k-1]);
if (!cand.insert(nums[i]).second) return true;
}
return false;
}