79. Repeat Within Reach
A security desk records the badge number of each visitor who enters a building, in order, in the array nums. A badge that is scanned twice in a short time may indicate that someone shared it with another person, so the desk flags such repeats.
Return true if there are two different positions i and j in nums with nums[i] == nums[j] and |i - j| <= k, and return false otherwise. When k is 0, only a position compared with itself would qualify, so the answer is false. Two positions are different if their indices are different, even if the values are equal.
Example 1
- Input:
- nums = [3,8,1,3,9], k = 3
- Output:
- true
- Explanation:
The value 3 appears at indices 0 and 3, which are 3 apart, and 3 <= k.
Example 2
- Input:
- nums = [3,8,1,3,9], k = 2
- Output:
- false
- Explanation:
The only repeated value is 3, but its two positions are 3 apart, which is more than k = 2.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109
0 ≤ k ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(min(n, k))