Intuition#

核心思路：維護一個大小最多為 k 的滑動視窗（HashSet），檢查新元素是否已在視窗中。

• 需要在距離 k 以內找到重複元素
• 用 HashSet 作為滑動視窗，保持視窗大小 <= k
• 當視窗超過 k 時，移除最早進入的元素

Approaches#

1: Brute Force - 雙層迴圈#

• 概念: 對每個 i，檢查 i+1 到 i+k 範圍內是否有相同元素
• 時間複雜度: O(n * k) - 最差情況
• 空間複雜度: O(1)

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#

• 概念: 用 HashSet 維護大小為 k 的視窗，每步加入新元素前檢查是否已存在；若視窗超過 k，移除最左邊的元素
• 時間複雜度: O(n) - 每個元素加入和移除各一次
• 空間複雜度: 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
    }
}

移除的是 nums[i - k] 而非 nums[i - k + 1]，因為新元素已加入後視窗大小為 k+1，要移除最早的那個。

🔑 Takeaways#

• Pattern: 固定大小滑動視窗 + HashSet
• 關鍵技巧: HashSet 同時作為視窗內容和查重工具；視窗大小上限為 k，超過就移除最左元素