LeetCode 刷題日記
EP.01

#1 Two Sum
從暴力解到 HashMap 思維

同一題三種解法，複雜度從 O(n²) 降到 O(n)

Joseph Chen
November 2023
Back to Blog
5 min read
1.2k views

Two Sum 是 LeetCode 上的第 1 題，也是幾乎所有人的第一題。題目很簡單：給一個整數陣列 nums 和一個目標值 target，找出兩個數字的 index，使它們相加等於 target。

題目範例

Input / Output
Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

說明: nums[0] + nums[1] = 2 + 7 = 9

Way 1：暴力解（Brute Force）

最直覺的想法：兩層迴圈，每兩個數字都試試看加起來等不等於 target。

Way1 — 暴力解 O(n²)
class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums) - 1):
            for y in range(i + 1, len(nums)):
                if nums[i] + nums[y] == target:
                    return i, y
⏱ Time: O(n²)💾 Space: O(1)

這是我想的第一個解法，也是最直覺的暴力破解。雖然正確，但效率最差。外層迴圈跑 n 次，內層迴圈再跑 n 次，總共 n² 次比較。

⚠️ 當 nums 有 10,000 個元素，最壞情況要比較 1 億次。面試時給出這個解沒問題，但面試官一定會要你優化。

Way 2：Two-Pass HashMap

關鍵思維轉換：與其「找兩個數字」，不如改成「對每個數字，去查有沒有它的搭檔」。搭檔 = target - nums[i]。

用 HashMap（Python 的 dict）把每個數字和它的 index 存起來，查詢只需要 O(1)。

Way2 — Two-Pass HashMap
class Solution:
    def twoSum(self, nums, target):
        numMap = {}

        # 第一輪：把所有數字和 index 存入 dict
        for i in range(len(nums)):
            numMap[nums[i]] = i

        # 第二輪：找每個數字的補數
        for i in range(len(nums)):
            complement = target - nums[i]
            # 補數存在，且不能是自己
            if complement in numMap and numMap[complement] != i:
                return [i, numMap[complement]]

        return []
⏱ Time: O(n)💾 Space: O(n)

用空間換時間的經典策略。多用了一個 dict（O(n) 空間），換來 O(n) 的時間。
注意 numMap[complement] != i 這個條件：確保找到的是不同的兩個 index，避免同一個元素被用兩次。

Way 3：One-Pass HashMap（最佳解）

再進一步：不需要先建好整個 dict，邊走邊查。

Way3 — One-Pass HashMap
class Solution:
    def twoSum(self, nums, target):
        numMap = {}  # value → index

        for i in range(len(nums)):
            complement = target - nums[i]

            # 先查有沒有搭檔
            if complement in numMap:
                return [numMap[complement], i]

            # 沒有就把自己存進去，等後面的數字來配對
            numMap[nums[i]] = i

        return []
⏱ Time: O(n)💾 Space: O(n)

One-Pass 的精妙之處：存進 dict 的每個數字，都是在「等待」未來某個數字來配對它。只需要一次遍歷。

三種解法比較

解法TimeSpace適合場景
Way 1 暴力解O(n²)O(1)理解題意用，面試別只給這個
Way 2 Two-PassO(n)O(n)好理解，分兩步走
Way 3 One-PassO(n)O(n)最佳，面試首選

Python 細節：型別提示與 class 語法

剛接觸 LeetCode 時，看到題目給的模板有點矇：

LeetCode 模板
class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        ...

nums: list[int]

參數型別提示（type hint）。Python 不強制，只是讓人看懂。list[int] 表示這是一個整數 list。

-> list[int]

回傳值型別提示。-> 後面說明這個函式會回傳什麼型別。同樣不強制，但能讓 IDE 幫你做靜態分析。

self

Python class 裡，每個 method 的第一個參數固定是 self，代表「這個 instance 本身」。LeetCode 用 class 包裝是慣例，實際解題邏輯都在 method 裡面。

HashMap 思維的核心

Two Sum 教會我的不只是這道題的解法，而是一種思維模式：

  • →遇到「查詢某個值存不存在」的需求，優先想 HashMap
  • →把問題轉換：「找兩個數」 = 「對每個數，查它的補數」
  • →用空間換時間是演算法最常見的優化策略

下一篇

EP.02 — Set vs Dict

Contains Duplicate 教你選對資料結構

LeetCode
Array
HashMap
Python
EP.01