LeetCode 220：Contains Duplicate III — 滑動窗口 + 桶排序思想

題目

給定整數數組 nums，判斷是否存在索引 i, j 使得：

• |nums[i] - nums[j]| ≤ t
• |i - j| ≤ k

核心思想：桶排序 + 滑動窗口

將數值空間劃分為寬度 w = t+1 的桶（t=0 時寬度 1）。編號 id = num / w（負數需調整）。

若兩數差值 ≤ t，則它們必在同一桶或相鄰桶。維護大小 ≤ k 的滑動窗口內的桶映射 id → value。

算法步驟

1. 遍歷 nums，計算 id = num / max(1, t)（t=0 避免除零）。
2. 檢查當前桶、左鄰桶、右鄰桶是否存在值且差值 ≤ t，存在則返回 true。
3. 將 (id, num) 加入 unordered_map。
4. 若窗口超過 k，刪除 nums[i-k] 對應的桶。

C++ 代碼

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {
        if (k < 1 || t < 0) return false;
        unordered_map bucket;  // long 防溢出
        long w = (long)t + 1;              // 桶寬
        for (int i = 0; i < nums.size(); ++i) {
            long id = nums[i] >= 0 ? nums[i] / w : (nums[i] + 1) / w - 1; // 負數修正
            if (bucket.count(id)
                || (bucket.count(id-1) && nums[i] - bucket[id-1] <= t)
                || (bucket.count(id+1) && bucket[id+1] - nums[i] <= t))
                return true;
            bucket[id] = nums[i];
            if (i >= k) {
                long oldId = nums[i-k] >= 0 ? nums[i-k] / w : (nums[i-k] + 1) / w - 1;
                bucket.erase(oldId);
            }
        }
        return false;
    }
};

關鍵細節

• 桶寬 w = t+1：保證同桶內任意兩數差值 ≤ t。
• 負數桶編號修正：C++ 整除向零截斷，負數需 (x+1)/w - 1 使桶連續分布。
• 用 long 存儲：id、value 及差值計算防 32 位溢出。
• 刪除舊桶：精確按 nums[i-k] 計算 oldId 刪除，避免誤刪同桶新值。

複雜度

• 時間：O(n) 平均（哈希表 O(1) 操作）。
• 空間：O(min(n, k))。

替代方案

• TreeSet (Java) / multiset (C++)：維護有序窗口，lower_bound(num-t) 查找 ≥ num-t 的最小值，檢查是否 ≤ num+t。時間 O(n log k)，代碼更簡短無桶編號麻煩。