Contains Duplicate II
Easy· fixed window· hash set
Problem
Return true if two different indices i and j hold the same value and are at most k apart, that is |i - j| <= k.
Examples
Input: nums = [1,2,3,1], k = 3
Output: true
The two 1s are exactly 3 positions apart.
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Constraints
- • 1 <= nums.length <= 10^5
- • 0 <= k <= 10^5
Hints & approach
Hint 1
You only care about the last k elements before the current one.
Hint 2
Keep those elements in a set that slides along with you.
Approachtry the hints first
Maintain a hash set containing the values in the window of the last k indices. For each index i, if nums[i] is already in the set, a close duplicate exists, so return true. Otherwise add nums[i], and if the set now covers more than k elements, remove nums[i - k]. If the loop finishes, no qualifying pair exists.
Time O(n) · Space O(min(n, k))