Given an integer array nums and an integer k, return trueif there are two distinct indicesi and j in the array such that nums[i] == nums[j] and abs(i - j) <= 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
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105
Solutions
Solution 1: Hash Table
We use a hash table $d$ to store the nearest index of the number it has visited.
We traverse the array nums. For the current element $nums[i]$, if it exists in the hash table, and the difference between its index and the current index is no larger than $k$, then return true. Otherwise, we add the current element into the hash table.
After the traversal, return false.
The time complexity is $O(n)$ and the space complexity is $O(n)$. Here $n$ is the length of array nums.