LeetCode Contains Duplicate：排序與哈希表兩種解法判斷陣列重複

題目大意

給定整數陣列 nums，判斷是否包含任意重複元素。至少一個值出現 ≥ 2 次回傳 true，否則 false。

解法一：排序後檢查相鄰元素

排序使相同元素相鄰。遍歷檢查 nums[i] == nums[i-1]。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return false;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < n; ++i)
            if (nums[i] == nums[i-1]) return true;
        return false;
    }
};

• 時間：O(n log n)（排序主導）。
• 空間：O(1) 或 O(log n)（排序棧空間）。修改原陣列。

解法二：哈希集合記錄出現元素

遍歷陣列，用 unordered_set 或 unordered_map 記錄已見元素。發現重複即回傳 true。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;
        for (int x : nums) {
            if (seen.count(x)) return true;
            seen.insert(x);
        }
        return false;
    }
};

• 時間：O(n) 平均。
• 空間：O(n)。不修改原陣列。

方案比較與選擇

延伸題目

• Contains Duplicate II：額外限制索引差 <= k，用哈希表記錄最新索引。
• Contains Duplicate III：額外限制值差 <= t 且索引差 <= k，用有序集合維護滑動窗口。