LeetCode Two Sum 解題詳解：哈希表單遍歷 O(n)

問題描述

給定整數數組 nums 和目標值 target，找到兩數下標使其和為 target。假設唯一解，下標從 1 開始（LeetCode 早期題目要求）。

哈希表法

遍歷數組，對每個 x = nums[i]，查找 target - x 是否已在表中。若在，直接返回；否則將 x 存入表（值為下標）。

vector twoSum(vector& nums, int target) {
    unordered_map mp; // 值 -> 下標(1-based)
    for (int i=0; i

關鍵細節

先查後存，避免同一元素被自己匹配（如 target=4, nums=[2] 不應匹配）。
下標存 1-based 符合題目輸出要求（現代 LeetCode 多為 0-based，需注意）。
unordered_map 平均 O(1) 查找/插入，總體 O(n)。


排序雙指針法（不保留原下標）
若不需返回原下標，可排序後雙指針夾逼，O(n log n) 時間，O(1) 空間（或 O(n) 存原下標）。

複雜度

時間 O(n)，空間 O(n)。
n ≤ 10^4 等規模極快。