LeetCode 219：存在重複元素 II（哈希表記錄索引差）

題目描述

給定整數數組和整數 k，判斷是否存在兩個不同索引 i、j 使得 nums[i] == nums[j] 且 |i - j| ≤ k。

哈希表單次遍歷

用 unordered_map 記錄每個數字最近出現的索引。遍歷數組，若當前數字已在表中且索引差 ≤ k 返回 true；否則更新該數字索引為當前位置。

代碼實現 (C++)

class Solution {
public:
    bool containsNearbyDuplicate(vector& nums, int k) {
        unordered_map pos;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = pos.find(nums[i]);
            if (it != pos.end() && i - it->second <= k) return true;
            pos[nums[i]] = i;
        }
        return false;
    }
};

複雜度

• 時間：O(n)
• 空間：O(n)