LeetCode: Contains Duplicate II

In Contains Duplicate problem, we just need to judge whether duplication exist, so set is enough.
Here, we need to search number to get index, so unordered_map(hashmap) will be first choice.

For each loop, if current number is in hashmap, this number appeared before. We calculate the index distance. If distance less or equal to k, return true. If distance is larger than k, we need to update index information in hashmap for current number.

Here is a point, there may be more than just two identical numbers in the array. So we need to update. If current number appears in the future, the future position to position now will be closer than to old position. So we just need to record the current position (corresponding to current number in Hashmap)

Complexity: O(nums.size)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int,int> Map; for(int i=0;i<nums.size();i++){ if(Map.find(nums[i])!=Map.end()) { int d=i-Map[nums[i]]; if (d<=k) return true; else Map[nums[i]]=i; } else Map[nums[i]]=i; } return false; } };

Reference:http://www.cnblogs.com/grandyang/p/4539680.html 
//codes in this blog doesn't work, because array can have more than two identical numbers.