LeetCode 1 Two Sum：哈希表 O(n) 求兩數之和

題目大意

給整數數組 nums 和目標值 target，找出兩數下標使其和為 target。假設唯一解，不重複使用同一元素。返回下標數組（順序不限）。

最優解：哈希表單次遍歷

• 遍歷數組，對每個 `num`，檢查 `target - num` 是否已在哈希表中。
  - 若在，直接返回 `[map[target-num], i]`。
  - 否則將 `num → i` 存入哈希表。
• 時間 O(n)，空間 O(n)。

代碼

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map map; // val -> index
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (map.count(complement)) {
                return {map[complement], i};
            }
            map[nums[i]] = i;
        }
        return {}; // 保證有解，不會執行
    }
};

替代方案：排序 + 雙指針（需保留原下標）

• 建立 `(value, index)` 對數組並按 value 排序。
• 雙指針 `l=0, r=n-1` 向中間收縮尋找和為 target 的 pair。
• 時間 O(n log n)，空間 O(n)。

總結

Two Sum 是哈希表應用的入門經典。**單次遍歷邊查邊存** 完美利用了「查找互補值」的特性，將 O(n²) 暴力優化為 O(n)。注意 C++ `unordered_map` 平均 O(1)，最壞 O(n) 但極難觸發；Java `HashMap` 同理。