LeetCode Contains Duplicate II：哈希表記錄索引判斷重複距離

題目大意

給定整數陣列 nums 與整數 k。判斷是否存在兩個不同索引 i, j 滿足：nums[i] == nums[j] 且 |i - j| <= k。存在回傳 true，否則 false。

解法：哈希表記錄最新索引

遍歷陣列，維護 unordered_map<int, int> map：鍵 = 元素值，值 = 該元素最近出現的索引。

• 對每個 nums[i]，若 map 中已存在，計算 i - map[nums[i]]。
• 若差值 <= k，直接回傳 true。
• 否則更新 map[nums[i]] = i（保留最近索引，因更早的索引與未來元素距離更大，不可能滿足條件）。
• 遍歷結束未發現，回傳 false。

關鍵優化

• 使用 unordered_map 而非 map，平均 O(1) 查詢/插入，整體 O(n) 時間。
• 邊界檢查：nums.size() < 2 || k < 1 直接回傳 false。

C++ 完整實現

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if (nums.size() < 2 || k < 1) return false;
        unordered_map<int, int> idxMap;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = idxMap.find(nums[i]);
            if (it != idxMap.end()) {
                if (i - it->second <= k) return true;
                it->second = i; // 更新為最新索引
            } else {
                idxMap.emplace(nums[i], i);
            }
        }
        return false;
    }
};

複雜度分析

• 時間：O(n) 平均，O(n^2) 最壞（哈希衝突極端情況）。
• 空間：O(min(n, k))，實際上最多儲存 k+1 個不同元素（滑動窗口視角）。

延伸：Contains Duplicate III

進階版要求 |nums[i] - nums[j]| <= t 且 |i - j| <= k，需用有序集合（set/multiset）維護滑動窗口內元素，查找區間 [x-t, x+t] 是否有元素，複雜度 O(n log k)。