LeetCode Two Sum 詳解：哈希表 O(n) 解法與同元素去重陷阱

算法演進

暴力法 O(n²)

雙層循環枚舉所有數對，時間復雜度 O(n²)，大數據下超時。

哈希表優化 O(n)

核心思想：遍歷數組時，將 數值 → 索引 存入哈希表。對於當前元素 x，查找 target - x 是否已存在。

關鍵陷阱：當 x == target - x（即 x = target/2）時，不能使用同一元素兩次。需檢查哈希表中存儲的索引是否與當前索引不同。

AC 代碼 (C++)

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        unordered_map<int, int> hash_map;  // 數值 -> 索引 (0-based)
        vector<int> result;

        // 第一遍：構建哈希表
        for (int i = 0; i < numbers.size(); ++i) {
            hash_map[numbers[i]] = i;
        }

        // 第二遍：查找互補數
        for (int i = 0; i < numbers.size(); ++i) {
            int complement = target - numbers[i];
            auto it = hash_map.find(complement);
            
            if (it != hash_map.end()) {
                int j = it->second;
                if (i != j) {  // 關鍵：排除同一元素
                    result.push_back(min(i, j) + 1);  // 轉 1-based
                    result.push_back(max(i, j) + 1);
                    return result;  // 題目保證唯一解，直接返回
                }
            }
        }
        return result;  // 理論上不會執行到這裡
    }
};

優化：單遍歷版本

邊構建哈希表邊查找，避免同元素問題（因為當前元素尚未加入表）：

vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (mp.count(complement)) {
            return {mp[complement] + 1, i + 1};
        }
        mp[nums[i]] = i;
    }
    return {};
}

複雜度對比

總結

• 哈希表將查找從 O(n) 降為 O(1)，總體 O(n)
• 單遍歷寫法更優雅：當前元素查找的是「之前見過的元素」，天然避免了使用同一元素兩次的問題
• 返回 1-based 索引需 +1，注意 index1 < index2 順序