LeetCode 1 兩數之和：哈希表實現 O(n) 最優解法全語言示範

問題描述

給定整數數組 nums 和目標值 target，找出兩數之和等於目標值的下標（1-based），保證唯一解。

兩種核心思路

暴力法 O(n²)

雙重循環枚舉所有數對，超時不可取。

哈希表法 O(n) —— 最優解

遍歷數組，對每個 x 查找 target - x 是否已存在哈希表中。哈希表存儲 值 -> 下標 映射。單次遍歷即可完成。

多語言實現

Java (HashMap)

public int[] twoSum(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i]))
            return new int[]{map.get(target - nums[i]), i + 1};
        map.put(nums[i], i + 1);
    }
    return null;
}

C++ (STL unordered_map)

vector twoSum(vector& nums, int target) {
    unordered_map mp;
    for (int i = 0; i < nums.size(); i++) {
        auto it = mp.find(target - nums[i]);
        if (it != mp.end()) return {it->second, i + 1};
        mp[nums[i]] = i + 1;
    }
    return {};
}

C (手寫哈希表)

鏈地址法實現簡易哈希表，含 put、get、contains 操作，代碼較長但原理相同。

Python (字典)

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

複雜度分析

• 時間：O(n)，單次遍歷，哈希操作均攤 O(1)
• 空間：O(n)，哈希表存儲

其他可行方向

• 排序 + 雙指針：O(n log n)，需保留原始下標
• 二叉搜索樹 / 平衡樹：O(n log n)，常數較大

總結

Two Sum 是哈希表「以空間換時間」的經典入門題。掌握單次遍歷同時查找與插入的技巧，可廣泛應用於各類配對查找問題。