LeetCode Two Sum：哈希表單次遍歷 O(n) 解法

問題描述

給定整數數組 nums 和目標值 target，找出兩數之和等於 target 的下標。假設唯一解，不可重複使用同一元素。

示例：nums=[2,7,11,15], target=9 → [0,1]

三種方案對比

哈希表單次遍歷算法

遍歷數組，對於當前元素 x，查找 target - x 是否已在哈希表中：

• 若在 → 找到答案，返回 [map[target-x], i]。
• 若不在 → 將 x 及其下標 i 存入哈希表，繼續。

關鍵點：先查後存，避免用同一元素兩次（如 target=4, nums=[2,...]）。

C++ 實現

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map mp; // 值 -> 下標
        for (int i = 0; i < nums.size(); ++i) {
            int need = target - nums[i];
            if (mp.count(need)) return {mp[need], i};
            mp[nums[i]] = i;
        }
        return {}; // 題目保證有解，不會執行到這裡
    }
};

Java 實現

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) return new int[]{map.get(need), i};
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No solution");
    }
}

Python 實現

class Solution:
    def twoSum(self, nums, target):
        mp = {}
        for i, x in enumerate(nums):
            need = target - x
            if need in mp: return [mp[need], i]
            mp[x] = i

進階考慮

• 重複元素：哈希表存儲最新下標或首次下標均可，因為題目保證唯一解。
• 有序數組變體：Two Sum II（輸入有序）→ 雙指針 O(n) 時間 O(1) 空間。
• 數據結構設計變體：Two Sum III → 支持 add 和 find 操作的類設計。

總結

Two Sum 是哈希表典型應用的入門題。核心模式：遍歷 + 查找互補值 + 存儲當前值。這種「以空間換時間、單次遍歷」的思想廣泛應用於「三數之和」、「四數之和」、「子數組和等於 K」等問題。