## 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*.

### Analysis:

Same idea as previous question that Hash table is used. The only difference if the requirement of minimum distance between the same elements is at most k.Remember that previous question, we set the value of hash table True/False, in this question, we change that to

*the index of element.*Therefore we can keep tracking the distance between the two elements. A simple check can solve the problem.

### Code(C++):

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { if (nums.size() == 0 ){ return false; } map<int,int> mp; for (int i=0;i<nums.size();i++){ if (mp.find(nums[i])==mp.end()){ mp[nums[i]] = i; }else{ if (i - mp[nums[i]] <= k){ return true; }else{ mp[nums[i]] = i; //Update the position } } } return false; } };

### Code(Python):

class Solution(object): def containsNearbyDuplicate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ if len(nums) == 0: return False mp = {} for i in range(len(nums)): # Note: here you cannot use "if not " # because if mp[nums[i]] == 0, if not will also return True if mp.get(nums[i]) == None: mp[nums[i]] = i elif (i - mp[nums[i]]) <= k: return True else: mp[nums[i]] = i return False

public class Solution {

ReplyDeletepublic boolean containsNearbyDuplicate(int[] nums, int k) {

HashMap map = new HashMap();

for (int i=0; i=k) {

return true;

}

map.put(nums[i], i);

}

return false;

}

}

The above was my java solution. It failed a test case with input ([99,99], 2). The expectation was true, but I think its wrong.