LeetCode 筆記：Contains Duplicate III — 滑動窗口 + Multiset O(n log k)

題目

給定整數陣列 nums，判斷是否存在 i ≠ j 使得 |nums[i]-nums[j]| ≤ t 且 |i-j| ≤ k。

核心思路：有序滑動窗口

• 維護大小 ≤ k 的窗口，保證下標差 ≤ k。
• 窗口內元素需快速查找「是否存在值在 [x-t, x+t] 範圍內」→ 有序容器。
• C++ multiset（紅黑樹）支援 lower_bound、插入、刪除均 O(log k)。

演算法流程

1. 遍歷 i = 0..n-1。
2. 若 i > k，從窗口刪除 nums[i-k-1]。
3. 在窗口中查找 lower_bound(nums[i] - t)，若迭代器有效且 *it - nums[i] ≤ t → 返回 true。
4. 插入 nums[i] 進窗口。
5. 遍歷結束返回 false。

C++ 實作

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {
        if (k < 1) return false;
        multiset window;  // 用 long long 防溢位
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (i > k) window.erase(window.find(nums[i - k - 1]));
            auto it = window.lower_bound((long long)nums[i] - t);
            if (it != window.end() && *it - nums[i] <= t) return true;
            window.insert(nums[i]);
        }
        return false;
    }
};

複雜度

• 時間：O(n log k)。
• 空間：O(k)。

避坑指南

1. t 可能為 0，lower_bound(x) 正確處理等值情況。
2. nums[i] - t 可能溢位 int，轉 long long。
3. window.erase(val) 會刪除所有等值元素，必須用 window.find(val) 刪除單一實例。
4. k=0 直接 false（題目要求 i≠j）。

系列關聯

• Contains Duplicate I：單純去重，unordered_set O(n)。
• Contains Duplicate II：等值且下標差 ≤ k，unordered_map O(n)。
• 本題 III：值差 ≤ t 且下標差 ≤ k，需有序統計結構。