LeetCode 217：存在重複元素 — 排序與哈希兩種解法

題目描述

給定一個整數數組，判斷是否存在重複元素。若任意值出現至少兩次返回 true，否則返回 false。

解法一：排序後相鄰比較

先排序，再檢查相鄰元素是否相等。

bool containsDuplicate(vector& nums) {
    if (nums.size() <= 1) return false;
    sort(nums.begin(), nums.end());
    for (size_t i = 1; i < nums.size(); ++i)
        if (nums[i] == nums[i-1]) return true;
    return false;
}

時間 O(n log n)，空間 O(1)（原地排序）。

解法二：哈希集合

遍歷數組，用 unordered_set 記錄已見元素，發現重複即返回。

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

時間 O(n) 平均，空間 O(n)。

進階：計數排序思想（適用於數值範圍較小）

先找最大最小值，分配計數陣列，遍歷檢查計數 > 1。但需注意數值範圍過大時記憶體壓力。

總結

• 通用場景推薦哈希集合，代碼簡潔且平均 O(n)。
• 若禁止額外空間，可用排序法。