https://leetcode.com/problems/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 absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1 Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2 Output: false
[Solution]
Using STL"set" as a sliding window.
For example:
Let's say k=3, then you should use a sliding window with size 4(=k+1) to scan the input array.
If two elements in the sliding window are identical,
it means they are identical and their distance is no greater than 3.
And you should return True under that condition.
If you scan through the entire array and nothing happen, then return False.
About the implementation, using STL "set" as the sliding window is a good idea.
During "sliding",
1.Remove the left element from window(because the window is moving to the right)
2.Check if the right element is identical to any one in the window.(return True if exist.)
3.Add the right element into the window
Let's say k=3, then you should use a sliding window with size 4(=k+1) to scan the input array.
If two elements in the sliding window are identical,
it means they are identical and their distance is no greater than 3.
And you should return True under that condition.
If you scan through the entire array and nothing happen, then return False.
About the implementation, using STL "set" as the sliding window is a good idea.
During "sliding",
1.Remove the left element from window(because the window is moving to the right)
2.Check if the right element is identical to any one in the window.(return True if exist.)
3.Add the right element into the window
---
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> ht;
for (int i=0; i<nums.size();i++)
{
if(i>k) ht.erase(nums[i-k-1]);
if(ht.find(nums[i])!=ht.end()) return true;
ht.insert(nums[i]);
}
return false;
}
};
