雜湊表面試題實戰#

雜湊表（Map/Set）是面試中最常用的資料結構之一，核心優勢是 O(1) 的查找效率。本節介紹三道經典面試題。

解題套路：遇到「查找」或「計數」問題，優先考慮使用雜湊表。

LeetCode 242：有效的字母異位詞#

題目#

判斷兩個字串是否為異位詞（Anagram）—— 字母相同、數量相同、順序可不同。

輸入：s = "anagram", t = "nagaram"
輸出：true

解法一：排序法#

將兩個字串排序後比較。

def isAnagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)
  • 時間複雜度：O(n log n)
  • 空間複雜度：O(n)

解法二：雜湊計數法#

統計每個字母出現的次數並比較。

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        count[c] = count.get(c, 0) - 1
        if count[c] < 0:
            return False
    return True
  • 時間複雜度：O(n)
  • 空間複雜度：O(1)（最多 26 個字母）

解法三：陣列優化#

當字元集固定（如只有小寫字母）時，用陣列代替雜湊表。

陣列優化程式碼
def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    count = [0] * 26
    for c in s:
        count[ord(c) - ord('a')] += 1
    for c in t:
        count[ord(c) - ord('a')] -= 1
        if count[ord(c) - ord('a')] < 0:
            return False
    return True

若題目未限制字元集（如包含 Unicode），應使用雜湊表而非固定大小陣列。

LeetCode 1：兩數之和 (Two Sum)#

題目#

找出陣列中和為 target 的兩個數的下標。

輸入：nums = [2, 7, 11, 15], target = 9
輸出：[0, 1]  // 因為 nums[0] + nums[1] = 9

解法一：暴力法#

兩層迴圈枚舉所有組合。

  • 時間複雜度：O(n²)
  • 空間複雜度：O(1)

解法二：雜湊表#

核心轉換：x + y = target → y = target - x

走訪時，查詢 target - x 是否已存在於雜湊表中。

def twoSum(nums: list, target: int) -> list:
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []
  • 時間複雜度：O(n)
  • 空間複雜度：O(n)

為何用 Map 而非 Set？

題目要求返回下標，Set 只能判斷存在性，無法記錄下標。

LeetCode 15：三數之和 (Three Sum)#

題目#

找出陣列中所有和為 0 的不重複三元組。

輸入：nums = [-1, 0, 1, 2, -1, -4]
輸出：[[-1, -1, 2], [-1, 0, 1]]

解法一：暴力法#

三層迴圈，時間複雜度 O(n³)。

解法二：雜湊表#

固定 a、b，查找 -(a+b) 是否存在。

  • 時間複雜度：O(n²)
  • 空間複雜度：O(n)

解法三：排序 + 雙指標（推薦）#

  1. 先排序
  2. 固定第一個數 a
  3. 用雙指標在剩餘區間找 b + c = -a
雙指標解法程式碼
def threeSum(nums: list) -> list:
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # 剪枝：最小值 > 0，不可能有解
        if nums[i] > 0:
            break
        # 去重：跳過重複的 a
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                # 去重：跳過重複的 b 和 c
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result
  • 時間複雜度：O(n²)
  • 空間複雜度：O(1)（不計輸出）

去重是關鍵！

  1. 外層去重：nums[i] == nums[i-1] 時跳過
  2. 內層去重：找到解後，跳過重複的 left 和 right

解題模式總結#

題型關鍵技巧時間複雜度
計數/頻率雜湊表計數O(n)
兩數之和雜湊表查找補數O(n)
三數之和排序 + 雙指標O(n²)
四數之和固定兩數 + 雙指標O(n³)

通用優化思路：

  • 暴力 O(n^k) → 雜湊表優化為 O(n^(k-1))
  • 有序資料 → 雙指標替代內層迴圈
Backward 雜湊演算法 樹結構 Forward