LeetCode 1. 兩數之和（Two Sum） - 暴力與哈希優化完整解析

題目重述

給定整數數組 nums 和目標值 target，找出兩個不同下標 i, j 使 nums[i] + nums[j] == target。假設恰好存在一組解，返回下標數組（0-based）。

方法一：暴力雙重循環 O(N²)

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] + nums[j] == target) 
                return new int[]{i, j};
        }
    }
    return null; // 題目保證有解，理論不可達
}

✅ 簡單直觀 ❌ N=10⁴ 時會超時。

方法二：單遍歷哈希表 O(N) — 推薦

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

核心思想：一邊遍歷一邊查詢「補數」是否已出現。因為先查後放，保證不會用同一元素兩次。

關鍵細節對比

擴展思考

• 有序數組：雙指針 O(N) O(1)，但會破壞原始下標，需額外記錄。
• 多組解/無解：返回 List 或拋出異常。
• 三數之和：排序 + 固定一數 + 雙指針 O(N²)。

總結

Two Sum 是哈希表「以空間換時間」的經典入門題。掌握 單遍歷+先查後放 模式，可直接套用到「四數之和 II」、「和為 K 的子數組」等變體。