219. Contains Duplicate II
2018-08-15 本文已影响0人
SilentDawn
Problem
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.
Example
Input: nums = [1,2,3,1], k = 3
Output: true
Input: nums = [1,0,1,1], k = 1
Output: true
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Code
static int var = [](){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}();
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int size = nums.size();
if(size<=1)
return 0;
map<int,int> dict;
for(int i = 0;i < size;i++)
{
if(dict.find(nums[i])!=dict.end()){
if(i - dict[nums[i]] <= k)
return true;
else
dict[nums[i]] = i;
}
else{
dict[nums[i]] = i;
}
}
return false;
}
};