# Leetcode: Contains Duplicate II

By | 2016 年 5 月 11 日

# Question

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 difference between i and j is at most k.

# Analyze

It’s strait forward to using dictionary on this question. First run, save position of each number in the dictionary; Second run, check the dictionary to see if there is another duplication in this array and check the position of it.
But there is a situation that need take into consideration, that the array may contain the duplication multiple times. To deal with this, just checking in the first run, to see if the last position (if any) is close enough.

# Code

## C++ code

```class Solution {
public:
inline int abs(int v) {
return v < 0 ? -v : v;
}
bool containsNearbyDuplicate(vector<int>& nums, int k) {
map<int, int> dict;
for(int i=0; i<nums.size(); ++i) {
if(dict.find(nums[i]) != dict.end()) {
if(abs(dict[nums[i]]-i) <= k)
return true;
}
dict[nums[i]]=i;
}
for(int j=0; j<nums.size(); ++j){
map<int,int>::iterator it = dict.find(nums[j]);
map<int,int>::iterator endit = dict.end();
if(endit != it){
int i = it->second;
if(i != j && abs(i-j) <= k)
return true;
}
}
return false;
}
};
```