Array & Hashing · 04 / 05

Hash Set / Map Patterns計數與去重

Two Sum、Group Anagrams 這類「用空間換時間」的模式。

用在：頻率統計、配對查找

時間複雜度O(n)

空間複雜度O(n)

難度入門

前置知識Hash Table

01為什麼需要它

找出兩筆加起來剛好等於目標的交易

對帳時要找「哪兩筆金額加起來是 1000」。兩層迴圈枚舉所有配對是 O(n²)，十萬筆就是一百億次。

為什麼用它走到每一筆時，問「我需要的那個數字之前出現過嗎」。把看過的存進雜湊表，這個問題就是 O(1)，整體 O(n)。這是 Two Sum，也是所有「配對查找」的原型。

搜尋引擎判斷兩個字是不是同一組字母

listen 和 silent 用了同樣的字母。拼字檢查、字謎遊戲、找重複的文件，都要快速判斷「內容一樣但順序不同」。

為什麼用它數每個字母出現幾次，兩邊的計數表一樣就是同一組。雜湊表讓計數是 O(n)；再把「排序後的字串」當作 key，就能把所有同組的字一次分好。

日誌裡出現最多次的錯誤是哪幾個

上億行 log，要找出前 10 名最常見的錯誤訊息。

為什麼用它雜湊表計數一遍 O(n)，再取前 k 名。「統計頻率」是雜湊表最常見的用法，之後配上堆積就是 Top-K 問題。

看到這些關鍵字就想到它：出現幾次、有沒有重複、找搭檔／配對、同一組的歸在一起、看過沒有、把 O(n²) 的內層迴圈換掉。

02核心概念

雜湊表本身只做一件事：O(1) 的「存」和「查」。它的威力來自一個固定套路：暴力解裡通常有一層內迴圈在「找某個東西」，把那層迴圈換成雜湊表查詢，O(n²) 就變成 O(n)。用 O(n) 的空間換掉一個 n。

幾乎所有題目都是四種模式之一。配對查找：走到 x 時查「我需要的 target − x 看過沒」（Two Sum）。計數：key 是元素、value 是次數（Valid Anagram、Top K Frequent）。分組：設計一個「同組的元素會算出一樣的 key」（Group Anagrams 用排序後的字串）。存在性檢查：先把所有東西丟進 set，之後任何「在不在」都 O(1)（Longest Consecutive Sequence）。

設計 key 是這類題的核心技巧。key 必須可雜湊（不可變：數字、字串、tuple，而不是 list），而且要「同組相同、不同組不同」。排序後的字串、26 個字母的計數 tuple、座標除以格子大小、前綴和的值，都是常見的 key。

03演算法步驟

1先寫出暴力解，找到那層「在找東西」的內迴圈。它在找什麼？那就是雜湊表的 key。
2決定 value 是什麼：只要知道「在不在」用 set；要位置用「值 → 索引」；要次數用「值 → 計數」；要分組用「key → list」。
3從左到右一趟掃過去：先查雜湊表能不能回答問題，再把目前的元素存進去。順序反過來會讓元素和自己配對。
4分組題先想 key：同一組的元素經過什麼運算會變成一樣的值？確認那個值是不可變的型別。
5驗證複雜度：n 次迴圈，每次 O(1) 查與存，整體 O(n) 時間、O(n) 空間。若內迴圈還在，代表 key 設計得不對。

04互動示範

逐步看 Two Sum 一趟掃過陣列：每一步先查「需要的搭檔」在不在表裡，不在就把自己存進去。注意找到答案時，整個陣列只看了一遍。

target = 12

nums

[0]4

[1]9

[2]2

[3]7

[4]11

[5]5

1def two_sum(nums, target):
2    seen = {}
3    for i, x in enumerate(nums):
4        need = target - x
5        if need in seen:
6            return [seen[need], i]
7        seen[x] = i

seen（值 → 索引）

空

步驟 0/12seen 是空的雜湊表，用來記「看過的數字 → 它的索引」。

05程式碼

四段程式碼對應四種模式。Python 的 Counter 和 defaultdict 是計數與分組的標準寫法；C++ 用 unordered_map 與 unordered_set。

from collections import Counter, defaultdict

# 模式一：配對查找。走到 x 時問「我需要的搭檔看過沒」
def two_sum(nums, target):
    seen = {}                         # 值 → 索引
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i                   # 先查再存，才不會和自己配對


# 模式二：計數。一個字元／一個數字出現幾次
def is_anagram(s, t):
    return Counter(s) == Counter(t)   # Counter 就是 dict[元素, 次數]

def top_k_frequent(nums, k):
    freq = Counter(nums)
    return [x for x, _ in freq.most_common(k)]


# 模式三：分組。設計一個「同組的東西算出來會一樣」的 key
def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))      # "eat", "tea", "ate" 都變成 "aet"
        groups[key].append(w)
    return list(groups.values())


# 模式四：用 set 做 O(1) 的「在不在」，把 O(n²) 壓成 O(n)
def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:            # x 是某段連續數字的起點才往上數
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best                       # 每個數字最多被走到兩次 → O(n)

06練習題

LeetCode 1Two Sum（配對）Easy
LeetCode 242Valid Anagram（計數）Easy
LeetCode 219Contains Duplicate II（值 → 最近索引）Easy
LeetCode 49Group Anagrams（分組）Medium
LeetCode 347Top K Frequent Elements（計數 + 桶或堆積）Medium
LeetCode 128Longest Consecutive Sequence（存在性）Medium

上一篇Hash Table 下一篇Matrix