常用 Algorithms

一小组 algorithm patterns 会反复出现：搜索、遍历 graphs、收缩 windows、caching，以及用 memory 换 time。

认出 pattern，比背问题名称更重要。
Input 形状 通常已经点名了工具。
下面每个 pattern 都附上精确的 TypeScript 实现与 complexity 说明。

Pattern 地图

Pattern	Typical input	Reach for it when
Hash map	Unsorted array / set	需要 O(1) lookups 或 frequency counts
Two pointers	Sorted array, or pair from ends	Linear scan 可以取代 nested loops
Sliding window	Array / string contiguous segment	Subarray 或 substring 约束
Binary search	Sorted array, or monotonic answer	Search space 每一步可以减半
Stack	Nested / matching structure	Latest-open / next-greater 问题
Linked list	Pointer-based sequence	Reverse、cycle、constant-space walks
Tree DFS / BFS	Binary / n-ary tree	Depth vs level-order 问题
Graph search	Grid or adjacency list	Connectivity、paths、components
Topological sort	Directed acyclic graph	带 prerequisites 的排序
Heap	Stream or “top K”	要 extremes 但不想完整 sort
Union-Find	Undirected connectivity	Merge components、detect cycles
Backtracking	Combinatorial search	建立所有 valid candidates
Dynamic programming	Overlapping subproblems	可重用的 optimal count / path
LRU	Cache with capacity	O(1) get/put 搭配 eviction

Hash Map：Two Sum

Hash map 把昂贵的 scan 变成 constant-time lookups。

function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>() // value -> index

  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    const j = seen.get(need)
    if (j !== undefined) return [j, i]
    seen.set(nums[i], i)
  }

  throw new Error("no pair sums to target")
}

twoSum([2, 7, 11, 15], 9) // [0, 1]

当你本来会 nest loops 去找 complement、数 frequencies，或记住「是否已经见过？」时，就用它。
Complexity: O(n) time, O(n) space.
同一个想法支撑 anagram checks（character counts 的 Map）以及 first-unique-character 问题。
Failure： 对本来可以 keyed 的 data 做 nested loops。

Two Pointers：Pair With Target (Sorted)

当 array 已 sorted，两个 indices 可以向内（或一起向前）移动，而不必用 nested loop 搜索。

function twoSumSorted(nums: number[], target: number): [number, number] {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) return [left, right]
    if (sum < target) left++
    else right--
  }

  throw new Error("no pair sums to target")
}

twoSumSorted([1, 2, 3, 4, 6], 6) // [1, 3] -> 2 + 4

移动那个能相对 target 减少 error 的 pointer。
Complexity: O(n) time, O(1) extra space（假设 array 已经 sorted）。
Failure： 在 unsorted array 上套 inward pointers——移动规则假定有序。

Sliding Window：Longest Substring Without Repeating Characters

Window 是一段 contiguous segment [left, right]，你一边 expand 一边 shrink，同时维持一个 invariant。

function lengthOfLongestSubstring(s: string): number {
  const lastIndex = new Map<string, number>()
  let left = 0
  let best = 0

  for (let right = 0; right < s.length; right++) {
    const ch = s[right]
    const prev = lastIndex.get(ch)
    if (prev !== undefined && prev >= left) {
      left = prev + 1
    }
    lastIndex.set(ch, right)
    best = Math.max(best, right - left + 1)
  }

  return best
}

lengthOfLongestSubstring("abcabcbb") // 3 ("abc")

用于 unique characters、sum ≤ K，或最多 K 个 distinct values——grow 与 shrink 一段 range，而不是从头开始。
Complexity: O(n) time, O(min(n, alphabet)) space.
Failure： shrink left 时没有检查 last occurrence 是否仍在 window 里。

Binary Search：Lower Bound

Binary search 反复把 monotonic search space 切成两半。

text

lo → mid → hi
mid:
  nums[mid] < target → lo = mid + 1
  else               → hi = mid

function lowerBound(nums: number[], target: number): number {
  let lo = 0
  let hi = nums.length // exclusive upper bound

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2)
    if (nums[mid] < target) lo = mid + 1
    else hi = mid
  }

  return lo
}

lowerBound([1, 3, 3, 5, 7], 3) // 1
lowerBound([1, 3, 3, 5, 7], 4) // 3 (insert before 5)

仔细的版本返回第一个满足 nums[i] >= target 的 index（lower bound / insertion point）。
当 array 本身未 sorted，但 answer 是 monotonic 的（例如能用的最小 capacity），就对 answer 做 binary search。
Complexity: O(log n) time, O(1) space.
Failure： 混用 inclusive 与 exclusive bounds——hi = nums.length 是 exclusive；hi = mid（不是 mid - 1）才能保住 invariant。

Stack：Valid Parentheses

Stack 存放「仍未关闭」的工作，并按 LIFO 顺序 pop。

function isValidParentheses(s: string): boolean {
  const pairs: Record<string, string> = {
    ")": "(",
    "]": "[",
    "}": "{",
  }
  const stack: string[] = []

  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch)
      continue
    }

    const expected = pairs[ch]
    if (!expected || stack.pop() !== expected) return false
  }

  return stack.length === 0
}

isValidParentheses("()[]{}") // true
isValidParentheses("(]") // false

Matching brackets、path simplification，以及 monotonic next-greater 问题，都会 push 与 pop。
Complexity: O(n) time, O(n) space.
Failure： 因为每个 closer 都匹配了就 return true，却没检查 stack 是否为空——剩下的 openers 仍然无效。

Linked List：Reverse and Cycle Detection

Linked-list 问题通常是小心的 pointer rewiring。

type ListNode = {
  val: number
  next: ListNode | null
}

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null
  let curr = head

  while (curr) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }

  return prev
}

function hasCycle(head: ListNode | null): boolean {
  let slow = head
  let fast = head

  while (fast?.next) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) return true
  }

  return false
}

两个经典：in place reverse 整条 list，以及用 Floyd’s tortoise and hare 侦测 cycle。
Complexity: reverse 是 O(n) time, O(1) space；cycle detection 是 O(n) time, O(1) space.
Failure： 在保存 next 之前就 rewire curr.next——list 的其余部分就没了。

Tree DFS and BFS：Depth and Level Order

Trees 是没有 cycles 的 graphs。DFS 往深处走；BFS 一层一层走。

type TreeNode = {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return []

  const result: number[][] = []
  const queue: TreeNode[] = [root]

  while (queue.length > 0) {
    const size = queue.length
    const level: number[] = []

    for (let i = 0; i < size; i++) {
      const node = queue.shift()!
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

text

Root
  ├─ Level1
  │    ├─ Level2
  │    └─ Level2
  └─ Level1
       └─ Level2

DFS 用 recursion 或显式 stack。BFS 用 queue——unweighted tree 上 shortest path 的通常选择。
BFS 在进入下一层之前走完当前层；DFS 沿一条 branch 走到 leaf 再 backtrack。
Complexity: 两者最坏都是 O(n) time 与 O(n) space（skewed tree 或很宽的 level）。
Failure： 问题是 unweighted tree 上的 shortest path 却用 DFS——那是 BFS。

Graph：Number of Islands

Grid 是一张 graph：每个 cell 是 node，四方向 neighbors 是 edges。

function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0

  const rows = grid.length
  const cols = grid[0].length
  let count = 0

  function sink(r: number, c: number): void {
    if (r < 0 || c < 0 || r >= rows || c >= cols) return
    if (grid[r][c] !== "1") return

    grid[r][c] = "0"
    sink(r + 1, c)
    sink(r - 1, c)
    sink(r, c + 1)
    sink(r, c - 1)
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        count++
        sink(r, c)
      }
    }
  }

  return count
}

numIslands([
  ["1", "1", "0", "0"],
  ["1", "0", "0", "1"],
  ["0", "0", "1", "1"],
]) // 3

用 DFS 或 BFS 做 flood-fill，计算 land 的 connected components。
Complexity: O(rows × cols) time，最坏 O(rows × cols) space 给 recursion stack。
Failure： 数 cells 而不是 connected components——flood-fill 必须把整座 island 标成 visited。

Topological Sort：Course Schedule

当 tasks 有 prerequisites 时，把它们建成 directed graph，并产出一个顺序，使得每条 edge u → v 都表示 u 在 v 之前。

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph: number[][] = Array.from({ length: numCourses }, () => [])
  const indegree = Array.from({ length: numCourses }, () => 0)

  for (const [course, pre] of prerequisites) {
    graph[pre].push(course)
    indegree[course]++
  }

  const queue: number[] = []
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i)
  }

  let taken = 0
  while (queue.length > 0) {
    const course = queue.shift()!
    taken++

    for (const next of graph[course]) {
      indegree[next]--
      if (indegree[next] === 0) queue.push(next)
    }
  }

  return taken === numCourses // false means a cycle exists
}

canFinish(2, [[1, 0]]) // true
canFinish(2, [
  [1, 0],
  [0, 1],
]) // false

Kahn’s algorithm 用 indegrees 与 queue。
Complexity: O(V + E) time, O(V + E) space.
Failure： 假定每张 directed graph 都有顺序——taken !== numCourses 表示有 cycle。

Heap：Top K Frequent Elements

Heap 高效地保住当前的 extreme。对「top K」来说，一个 size-K 的 frequencies min-heap，可以避免 sort 整张 map。

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>()
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1)

  type Item = { value: number; count: number }
  const heap: Item[] = []

  const siftUp = (i: number) => {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2)
      if (heap[parent].count <= heap[i].count) break
      ;[heap[parent], heap[i]] = [heap[i], heap[parent]]
      i = parent
    }
  }

  const siftDown = (i: number) => {
    while (true) {
      let smallest = i
      const left = 2 * i + 1
      const right = 2 * i + 2
      if (left < heap.length && heap[left].count < heap[smallest].count) {
        smallest = left
      }
      if (right < heap.length && heap[right].count < heap[smallest].count) {
        smallest = right
      }
      if (smallest === i) break
      ;[heap[smallest], heap[i]] = [heap[i], heap[smallest]]
      i = smallest
    }
  }

  for (const [value, count] of freq) {
    heap.push({ value, count })
    siftUp(heap.length - 1)
    if (heap.length > k) {
      heap[0] = heap.pop()!
      siftDown(0)
    }
  }

  return heap.map((item) => item.value)
}

topKFrequent([1, 1, 1, 2, 2, 3], 2) // [1, 2] (order among ties may vary)

在 stream 或「top K」上，当你需要 extremes 却不想完整 sort 时，就用它。
Complexity: O(n log k) time，frequency map 占 O(n) space（heap 最多持有 k 个 items）。
Failure： 当 size-K heap 就够时，却去 sort 整张 frequency map。

Union-Find：Connected Components

Union-Find（Disjoint Set Union）维护一份把 elements 分成 components 的 partition。

class UnionFind {
  private parent: number[]
  private rank: number[]
  components: number

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i)
    this.rank = Array.from({ length: n }, () => 0)
    this.components = n
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]) // path compression
    }
    return this.parent[x]
  }

  union(a: number, b: number): boolean {
    const ra = this.find(a)
    const rb = this.find(b)
    if (ra === rb) return false // already connected — edge is redundant

    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra
    else {
      this.parent[rb] = ra
      this.rank[ra]++
    }

    this.components--
    return true
  }
}

function countComponents(n: number, edges: number[][]): number {
  const uf = new UnionFind(n)
  for (const [a, b] of edges) uf.union(a, b)
  return uf.components
}

countComponents(5, [
  [0, 1],
  [1, 2],
  [3, 4],
]) // 2

find 返回 representative；union 合并两个 sets。
Path compression + union by rank 让 operations 接近 amortized O(1)。
Complexity: n 个 nodes 与 m 条 edges 实际上是 O(n + m α(n))——α 是 inverse Ackermann function（实务上很小）。
Failure： union 之前没有先 find——你合并的是 nodes 而不是它们的 roots，partition 就破了。

Backtracking：Subsets

Backtracking 增量建立 candidates，并在探索下一条 branch 时撤销上一次选择。

function subsets(nums: number[]): number[][] {
  const result: number[][] = []
  const path: number[] = []

  function dfs(start: number): void {
    result.push([...path])

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i])
      dfs(i + 1)
      path.pop()
    }
  }

  dfs(0)
  return result
}

subsets([1, 2, 3])
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

用于 subsets、permutations、combinations，以及 constraint search。
Complexity: 产生并 copy 所有 subsets 是 O(n · 2ⁿ) time，recursion path 额外 O(n) space（不含 output）。
Failure： 忘了 path.pop()——后面的 branches 会共享一份被 mutate 的 path。

Dynamic Programming：Climbing Stairs and Unique Paths

当问题有 optimal substructure 与 overlapping subproblems 时，用 dynamic programming：较小的 pieces 只解一次，再重用。

从 base cases 出发往上建。
Failure： 子问题重叠时却 recurse 而不 reuse——那是 exponential，不是 DP。

1D：climbing stairs

你可以爬 1 或 2 步。到达 n 的 ways = 到达 n - 1 的 ways + 到达 n - 2 的 ways。

function climbStairs(n: number): number {
  if (n <= 2) return n

  let prev2 = 1
  let prev1 = 2

  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2
    prev2 = prev1
    prev1 = curr
  }

  return prev1
}

climbStairs(5) // 8

Complexity: O(n) time, O(1) space.

2D：unique paths

在 m × n grid 上，你只能向右或向下。到 (r, c) 的 paths = 从上方来的 paths + 从左方来的 paths。

function uniquePaths(m: number, n: number): number {
  const dp = Array.from({ length: m }, () => Array.from({ length: n }, () => 1))

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    }
  }

  return dp[m - 1][n - 1]
}

uniquePaths(3, 7) // 28

Complexity: O(m · n) time, O(m · n) space（用 rolling row 可压到 O(n)）。

LRU Cache

LRU cache 以 O(1) 返回 values，满了就驱逐 least recently used key。

class LRUCache {
  private readonly capacity: number
  private readonly map = new Map<number, number>()

  constructor(capacity: number) {
    this.capacity = capacity
  }

  get(key: number): number {
    if (!this.map.has(key)) return -1
    const value = this.map.get(key)!
    this.map.delete(key)
    this.map.set(key, value) // move to most-recently used
    return value
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) this.map.delete(key)
    this.map.set(key, value)

    if (this.map.size > this.capacity) {
      const oldest = this.map.keys().next().value as number
      this.map.delete(oldest)
    }
  }
}

const cache = new LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1) // 1
cache.put(3, 3) // evicts key 2
cache.get(2) // -1

在现代 JavaScript 里，Map 保留 insertion order，所以每次 access 把 key 移到末尾，就能实现 LRU，而不必手写 doubly linked list。
Complexity: amortized O(1) get 与 put；O(capacity) space.
Failure： get 只读却没有 delete + set——insertion order 就不再追踪 recency。

选择 Pattern

选 invariant 最清楚的那个 pattern，然后在写 code 之前先说出 time 与 space。

需要 fast lookup 或 frequency count？ Hash map。
Array 已 sorted，在找 boundary 或 pair？ Binary search 或 two pointers。
带约束的 contiguous subarray / substring？ Sliding window。
Matching 或 nested structure / next greater？ Stack。
Unweighted graph 的 shortest path 或 level-order tree？ BFS。
探索所有 paths、components 或 hierarchies？ DFS。
DAG 上的 prerequisites / ordering？ Topological sort。
大量 merges 的 connectivity？ Union-Find。
Top K 或 running extreme？ Heap。
Overlapping subproblems 加上 optimal reuse？ Dynamic programming。
在约束下产生所有 candidates？ Backtracking。
带 recency 的 bounded cache？ LRU。

要点

先掌握这些 patterns，再去追 exotic algorithms。大多数日常问题都是 hash maps、windows、binary search、graph traversal、heaps 与 DP 的重组。

对每一个解，要能说出 pattern、time 与 space complexity，以及如果 input 是 sorted、streaming，或大到放不进 memory，会怎么变。
专门工具（KMP、Bloom filters、consistent hashing）在更窄的领域才重要。上面这些 patterns 才是共享的 baseline。
Failure： 优化 nested loops，而真正的瓶颈是从未被衡量过的 network round trip。Complexity 是决策工具，不是竞技。

Recap Q&A

阅读下一篇笔记

Full-Stack Q&A