給定整數陣列
nums和整數k，判斷是否存在兩個不同的索引i和j，使得nums[i] == nums[j]且|i - j| <= k。
Example:
Input: nums = [1,2,3,1], k = 3 Output: true
Intuition
TIP
核心思路：維護一個大小最多為 k 的滑動視窗（HashSet），檢查新元素是否已在視窗中。
- 需要在距離 k 以內找到重複元素
- 用 HashSet 作為滑動視窗，保持視窗大小 <= k
- 當視窗超過 k 時，移除最早進入的元素
Approaches
1. Brute Force - Double Loop — O(n * k) / O(1)
- Idea: 對每個 i，檢查 i+1 到 i+k 範圍內是否有相同元素
- Time:
O(n * k)- 最差情況 - Space:
O(1)
Brute Force Code
class Solution {
fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
for (i in nums.indices) {
for (j in i + 1..minOf(i + k, nums.size - 1)) {
if (nums[i] == nums[j]) return true
}
}
return false
}
}⭐ 2. Sliding Window + HashSet — O(n) / O(k)
- Idea: 用 HashSet 維護大小為 k 的視窗，每步加入新元素前檢查是否已存在；若視窗超過 k，移除最左邊的元素
- Time:
O(n)- 每個元素加入和移除各一次 - Space:
O(k)- HashSet 最多存 k 個元素
class Solution {
fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
val window = HashSet<Int>()
for (i in nums.indices) {
if (nums[i] in window) return true
window.add(nums[i])
if (window.size > k) {
window.remove(nums[i - k])
}
}
return false
}
}WARNING
移除的是 nums[i - k] 而非 nums[i - k + 1]，因為新元素已加入後視窗大小為 k+1，要移除最早的那個。
🔑 Takeaways
- Pattern: 固定大小滑動視窗 + HashSet
- Key trick: HashSet 同時作為視窗內容和查重工具；視窗大小上限為 k，超過就移除最左元素