LeetCode 220 存在重復元素 III 題解

題目描述

給定一個整數數組 nums 和兩個整數 k 和 t，請判斷數組中是否存在兩個不同的索引 i 和 j，使得：

1. abs(nums[i] - nums[j]) <= t
2. abs(i - j) <= k

方法思路：桶排序 + 滑動窗口

核心思想

1. 桶排序思想：將數值范圍劃分為大小為t+1的桶

   • 每個元素根據值分配到對應的桶（編號 = 值 // (t+1)）

   • 同一桶內的元素自然滿足差值條件

   • 相鄰桶的元素需要額外驗證差值，
     相鄰桶要驗證額外差值的具體原因和實現邏輯：

     1.1 桶的劃分方式 每個桶的寬度是 t + 1 （w = t + 1），桶編號通過 數值 // w 計算得到。這種劃分方式導致：

       - 同一桶內元素的差值 一定 ≤ t （自動滿足條件）- 相鄰桶中元素 可能滿足差值 ≤ t
     

     1.2. 邊界情況示例 假設 t=3（w=4），數值分布：

       - 桶0：[0-3]- 桶1：[4-7]- 桶-1：[-4--1]當出現：- 數值3（桶0）和4（桶1） → 差1 ≤ 3- 數值-1（桶-1）和0（桶0） → 差1 ≤ 3
     

     1.3 必須顯式驗證的原因 相鄰桶中的元素不一定滿足差值條件（比如桶0的3和桶1的7差4>3），因此需要通過 abs(nums[i] - bucket_value) < w 的二次驗證，確保實際差值 ≤ t
     1.4. 算法完整性 這種設計保證三種可能性都被覆蓋：

       - ? 同桶元素 → 直接返回- ? 左鄰桶元素 → 驗證后返回- ? 右鄰桶元素 → 驗證后返回
     

2. 滑動窗口：維護大小為k的窗口

   • 使用字典記錄當前窗口內的元素
   • 當窗口超過k個元素時，刪除最早進入的元素

算法步驟

1. 處理非法輸入（t < 0）
2. 初始化桶字典和桶寬度w = t + 1
3. 遍歷數組元素：
   • 計算當前元素的桶編號
   • 檢查當前桶和相鄰桶是否滿足條件
   • 維護滑動窗口大小（刪除過期元素）

復雜度分析

• 時間復雜度：O(n)，每個元素處理時間為O(1)
• 空間復雜度：O(min(n,k))，滑動窗口最多保存k個元素

關鍵點說明

1. 桶寬度選擇：t+1的寬度保證了：

   • 同一桶內元素差≤t
   • 相鄰桶元素需要顯式驗證差值

2. 滑動窗口維護：

   if i >= k:expired_bucket = nums[i - k] // wdel bucket[expired_bucket]
   

這保證了任何時候桶中只包含最近k個元素

3. 負數處理 ：Python的整數除法是向下取整，例如：
   • -3 // 4 = -1 （而正數3//4=0）
   • 這確保了相鄰負數的正確分桶

示例輸入

nums = [1, 5, 9, 1, 5, 9]
k = 2
t = 3

輸出應為False，因為雖然存在相同元素，但索引差超過k的限制

LeetCode 220 存在重復元素 III

https://leetcode.cn/problems/7WqeDu/

解法：桶排序 + 滑動窗口 時間復雜度O(n) 空間復雜度O(min(n,k))

# LeetCode 220 存在重復元素 III
# https://leetcode.cn/problems/7WqeDu/
# 解法：桶排序 + 滑動窗口 時間復雜度O(n) 空間復雜度O(min(n,k))from typing import Listclass Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:"""判斷數組中是否存在滿足以下條件的兩個不同索引i,j：1. abs(nums[i] - nums[j]) <= t2. abs(i - j) <= k參數:nums: 輸入數組k: 索引最大差值（滑動窗口大小）t: 數值最大差值返回:bool: 是否存在滿足條件的元素對"""if t < 0:  # 處理非法輸入，t不能為負數return Falsen = len(nums)bucket = {}  # 用字典維護桶，鍵為桶編號，值為桶中元素值w = t + 1    # 桶的寬度（避免t=0時除零錯誤）for i in range(n):# 計算當前元素所屬的桶編號bucket_id = nums[i] // w  # 整數除法自動向下取整# 檢查當前桶是否已有元素（保證數值差<=t）if bucket_id in bucket:return True# 檢查左側相鄰桶（需要額外驗證數值差）if (bucket_id - 1) in bucket and abs(nums[i] - bucket[bucket_id - 1]) < w:return True# 檢查右側相鄰桶（需要額外驗證數值差）if (bucket_id + 1) in bucket and abs(nums[i] - bucket[bucket_id + 1]) < w:return True# 將當前元素加入桶bucket[bucket_id] = nums[i]# 維護滑動窗口，當i>=k時刪除最早進入桶的元素if i >= k:expired_bucket = nums[i - k] // wdel bucket[expired_bucket]return Falseif __name__ == "__main__":# 測試用例（題目示例）nums = [1, 5, 9, 1, 5, 9]k = 2t = 3print(Solution().containsNearbyAlmostDuplicate(nums, k, t))  # 預期輸出：False