LeetCode Q219: 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.

The key is to keep updating hash table when duplicate is met.

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

view raw Q219ContainsDuplicate.cpp hosted with ❤ by GitHub

Round 2 solution:

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

view raw Q219Rnd2.cpp hosted with ❤ by GitHub