LeetCode 兩數之和 - 哈希表 O(n) 解法

問題描述

給定整數數組和目標值 target，找出兩個數使其和等於 target，返回其下標（1-based），假設唯一解。

解法：哈希表一遍掃描

遍歷數組，對於每個元素 x，檢查 target-x 是否已在哈希表中。若在，直接返回；否則將 x 存入哈希表。時間 O(n)，空間 O(n)。

代碼實現（C++）

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map map; // 值 -> 下標
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (map.count(complement)) {
                return {map[complement] + 1, i + 1}; // 1-based
            }
            map[nums[i]] = i;
        }
        return {}; // 題目保證有解
    }
};

注意事項

• 先查後存，避免同一元素被使用兩次（如 target=4, nums=[2,...]）。
• 返回下標需按題目要求 1-based 且 index1 < index2。
• 若有重複元素，哈希表存儲最早出現的下標，不影響正確性。

變體：有序數組雙指針

若數組已排序，可用左右指針 O(n) 時間 O(1) 空間。但本題數組無序，哈希表最優。