🗂️ Arrays & Hashing

陣列與雜湊表——把相似的事物放一起，用索引或鍵值在 O(1) 找到它。

62 題 · 1 篇導讀

📖 分類導讀

相似的事物放一起，是讓環境井然有序的關鍵，這也是電腦世界中陣列（Array）此資料結構的設計理念。 因為事物都在同處，我們可藉索引在常數時間（O(1)）內找到對應元素（隨機存取）。

如果不是相似的事物，如果不放在一起，我們還有方法能好好整理它們嗎？可以，用鍵（Key）值（Value）架構即可。 我們先定好一個雜湊（Hashing）函數，讓要管理的事物都依循此函數的判斷放到對應區塊中。這樣就能在常數時間（O(1)）內找到鍵所對應的值。

Notes:

  • 有時反向遍歷陣列，做法會簡單很多
  • 程式碼要一開始就簡潔很難，寫完再整理比較容易
  • 善用陣列索引的有序性，有時會比雜湊表還好用

Hash Map 與 Hash Set

兩者底層都是雜湊，差別在「存不存值」：

  • Hash Set：只記「在不在」。用於去重、標記已造訪 (visited)、查詢存在性。
  • Hash Map：記「鍵對應到什麼」。用於計數（頻率表）、建立索引（值 → 位置）、快取中間結果。

看到「frequency / 出現次數」「unique / 去重」「快速查找 / 是否存在」「兩數配對」這類字眼，第一反應就該是雜湊。

複雜度

操作平均最壞
插入 / 查找 / 刪除O(1)O(n)

平均 O(1) 的前提是雜湊函數把元素夠均勻地散開；當大量鍵碰撞（雜湊到同格）時退化成 O(n)。面試通常假設 O(1)，但要知道這個前提存在。

常用技法

  • 配對查找（空間換時間）：邊遍歷邊把已看過的數存進 Map，查補數只要 O(1)，把 O(n^2) 的巢狀迴圈降為 O(n)。
  • 正規化鍵 (canonical key)：把「等價的東西」映到同一個鍵再分組。例如分組 anagram 時，用「排序後的字串」或「26 個字母的計數」當鍵。
  • 資訊指紋去重：對長字串/物件取雜湊當「指紋」，比逐字比對快；代價是極小機率的碰撞（生日悖論：鍵越多碰撞機率上升越快），對正確性要求高時需再驗證。

IMPORTANT

雜湊表不支援範圍查詢（找出「介於 a 與 b 之間的所有鍵」）。需要範圍、前驅後繼、第 k 小時，得改用有序結構（排序陣列 + 二分、平衡樹）。這正是「陣列索引有序性有時勝過雜湊表」的深層原因。

本章深入

  • 前綴和 (Prefix Sums)：用預處理把「子陣列和」查詢降到 O(1)，並搭配 Hash Map 求「和為 k 的子陣列」。

跨倉庫導讀

📘Prefix Sums
#1Two SumEasy★★★★★⏱ O(n)#14Longest Common PrefixEasy★★★★★⏱ O(S)#27Remove ElementEasy★★★★★⏱ O(n)#28Find The Index of The First Occurrence in a StringEasy★★★★★⏱ O(n + m)#31Next PermutationMedium★★★★★⏱ O(n)#36Valid SudokuMedium★★★★★⏱ O(1)#41First Missing PositiveHard★★★★★⏱ O(n)#49Group AnagramsMedium★★★★★⏱ O(n * k)#58Length of Last WordEasy★★★★★⏱ O(n)#68Text JustificationHard★★★★★⏱ O(n * maxWidth)#75Sort ColorsMedium★★★★★⏱ O(n)#118Pascals TriangleEasy★★★★★⏱ O(numRows^2)#122Best Time to Buy And Sell Stock IIMedium★★★★★⏱ O(n)#128Longest Consecutive SequenceMedium★★★★★⏱ O(n)#169Majority ElementEasy★★★★★⏱ O(n)#179Largest NumberMedium★★★★★⏱ O(n log n * k)#187Repeated DNA SequencesMedium★★★★★⏱ O(n)#205Isomorphic StringsEasy★★★★★⏱ O(n^2)#217Contains DuplicateEasy★★★★★⏱ O(n)#238Product of Array Except SelfMedium★★★★★⏱ O(n)#242Valid AnagramEasy★★★★★⏱ O(n)#271Encode and Decode StringsMedium★★★★★⏱ O(n)#280Wiggle SortMedium★★★★★⏱ O(n)#290Word PatternEasy★★★★★⏱ O(n)#303Range Sum Query - ImmutableEasy★★★★★⏱ O(n)#304Range Sum Query 2D ImmutableMedium★★★★★⏱ O(m*n)#307Range Sum Query - MutableMedium★★★★★⏱ O(log n)#347Top K Frequent ElementsMedium★★★★★⏱ O(n)#380Insert Delete Get Random O(1)Medium★★★★★⏱ O(1)#392Is SubsequenceEasy★★★★★⏱ O(n)#438Find All Anagrams in a StringMedium★★★★★⏱ O(n)#448Find All Numbers Disappeared in An ArrayEasy★★★★★⏱ O(n)#496Next Greater Element IEasy★★★★★⏱ O(n + m)#523Continuous Subarray SumMedium★★★★★⏱ O(n)#535Encode and Decode TinyURLMedium★★★★★⏱ O(1)#554Brick WallMedium★★★★★⏱ O(n * m)#560Subarray Sum Equals KMedium★★★★★⏱ O(n)#605Can Place FlowersEasy★★★★★⏱ O(n)#665Non Decreasing ArrayMedium★★★★★⏱ O(n)#705Design HashSetEasy★★★★★⏱ O(1)#706Design HashMapEasy★★★★★⏱ O(1)#724Find Pivot IndexEasy★★★★★⏱ O(n)#838Push DominoesMedium★★★★★⏱ O(n)#912Sort an ArrayMedium★★★★★⏱ O(n log n)#929Unique Email AddressesEasy★★★★★⏱ O(n * m)#1189Maximum Number of BalloonsEasy★★★★★⏱ O(n)#1299Replace Elements With Greatest Element On Right SideEasy★★★★★⏱ O(n)#1396Design Underground SystemMedium★★★★★⏱ O(1)#1461Check if a String Contains all Binary Codes of Size KMedium★★★★★⏱ O(n)#1603Design Parking SystemEasy★★★★★⏱ O(1)#1822Sign of An ArrayEasy★★★★★⏱ O(n)#1929Concatenation of ArrayEasy★★★★★⏱ O(n)#1930Unique Length 3 Palindromic SubsequencesMedium★★★★★⏱ O(26 * n)#1963Minimum Number of Swaps to Make The String BalancedMedium★★★★★⏱ O(n)#2001Number of Pairs of Interchangeable RectanglesMedium★★★★★⏱ O(n log(max(w,h)))#2002Maximum Product of The Length of Two Palindromic SubsequencesMedium★★★★★⏱ O(3^n)#2017Grid GameMedium★★★★★⏱ O(n)#2215Find the Difference of Two ArraysEasy★★★★★⏱ O(n + m)#2306Naming a CompanyHard★★★★★⏱ O(n * m + 26^2 * n)#2348Number of Zero-Filled SubarraysMedium★★★★★⏱ O(n)#2405Optimal Partition of StringMedium★★★★★⏱ O(n)#2483Minimum Penalty for a ShopMedium★★★★★⏱ O(n)