LeetCode 解題思路：1. Two Sum（兩數之和）

題目描述

給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那兩個整數，並返回它們的陣列索引。

你可以假設每種輸入只會對應一個答案。但是，陣列中同一個元素不能使用兩遍。

範例：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9，返回 [0, 1]

解法一：暴力解法（Brute Force）

思路

最直觀的方法是使用兩層迴圈，檢查所有可能的數字組合。

程式碼

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

複雜度分析

• 時間複雜度：O(n²)
  • 外層迴圈執行 n 次
  • 對於每個元素，內層迴圈平均執行 n/2 次
  • 總計約 n × n/2 = O(n²)
• 空間複雜度：O(1)
  • 只使用了常數個變數（i, j），不隨輸入規模增長

優缺點

• ✅ 簡單直觀，容易理解和實現
• ✅ 不需要額外的空間
• ❌ 時間效率低，當陣列很大時會很慢

解法二：兩次遍歷 Hash Table

思路

利用 Hash Table 將查找時間從 O(n) 降低到 O(1)。

1. 第一次遍歷：建立每個數字到其索引的映射
2. 第二次遍歷：查找每個數字的補數是否存在

程式碼

def twoSum(nums, target):
    # 第一次遍歷：建立 hash table
    hashmap = {}
    for i in range(len(nums)):
        hashmap[nums[i]] = i
    
    # 第二次遍歷：查找補數
    for i in range(len(nums)):
        complement = target - nums[i]
        if complement in hashmap and hashmap[complement] != i:
            return [i, hashmap[complement]]
    
    return []

複雜度分析

• 時間複雜度：O(n)
  • 第一次遍歷：n 次插入操作，每次 O(1) = O(n)
  • 第二次遍歷：n 次查找操作，每次 O(1) = O(n)
  • 總計：O(n) + O(n) = O(n)
• 空間複雜度：O(n)
  • Hash table 最多存儲 n 個鍵值對

關鍵理解：為什麼 Hash Table 查找是 O(1)？

Hash Table 使用雜湊函數直接計算元素的存儲位置，不需要逐一比對：

查找 7 in hashmap：
1. 計算 hash(7) = 某個位置
2. 直接訪問該位置
3. 不需要遍歷整個 table！

解法三：一次遍歷 Hash Table（最優解）

思路

邊遍歷邊查找，在同一次迴圈中完成：

1. 先檢查當前數字的補數是否已在 hash table 中
2. 如果不在，將當前數字加入 hash table

程式碼

def twoSum(nums, target):
    hashmap = {}
    
    for i in range(len(nums)):
        complement = target - nums[i]
        
        # 先查找
        if complement in hashmap:
            return [hashmap[complement], i]
        
        # 後加入
        hashmap[nums[i]] = i
    
    return []

演算過程示例

陣列：[2, 7, 11, 15]，目標：9

i=0, nums[0]=2:
  - complement = 9-2 = 7
  - 7 在 hashmap？否
  - 加入：hashmap = {2: 0}

i=1, nums[1]=7:
  - complement = 9-7 = 2
  - 2 在 hashmap？是！位置 0
  - 返回 [0, 1] ✓

複雜度分析

• 時間複雜度：O(n)
  • 最壞情況遍歷整個陣列一次
  • 每次迭代中的查找和插入都是 O(1)
• 空間複雜度：O(n)
  • 最壞情況 hash table 存儲 n-1 個元素

為什麼這樣可行？

關鍵洞察：對於任意一對解 (i, j)，當我們遍歷到較大的索引時，較小的索引已經在 hash table 中了！

三種解法比較

重要觀念總結

1. 時間與空間的權衡：我們用 O(n) 的額外空間換取了時間效率從 O(n²) 提升到 O(n)

2. Hash Table 的威力：將查找操作從 O(n) 降到 O(1) 是許多演算法優化的關鍵

3. 演算法優化的層次：

   • 第一步：實現功能（暴力解）
   • 第二步：優化時間複雜度（Hash Table）
   • 第三步：優化實際執行效率（一次遍歷）

練習建議

1. 先自己實現暴力解，確保理解問題
2. 思考如何優化查找過程
3. 試著手動模擬 Hash Table 的運作
4. 比較不同解法在大數據集上的實際執行時間

這道題是理解 Hash Table 應用的經典例題，掌握這三種解法的演進過程，對於解決其他類似問題很有幫助！