本文整理面试编程题中最常见的解题思路与代码框架，作为刷题时的参考索引。

1. 双指针 (Two Pointers)

适用场景：有序数组/链表中找满足条件的两个元素；原地修改数组。

  • 对撞指针：左右向中间靠拢，常见于两数之和、三数之和、去重。
  • 同向快慢指针：慢指针维护结果边界，快指针遍历，常见于链表找环、原地删除元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 对撞指针模板
left, right = 0, len(arr) - 1
while left < right:
    if condition(arr[left], arr[right]):
        # 记录/处理
        left += 1
        right -= 1
    elif too_small:
        left += 1
    else:
        right -= 1

# 快慢指针模板（原地去重）
slow = 0
for fast in range(len(arr)):
    if arr[fast] != arr[slow]:
        slow += 1
        arr[slow] = arr[fast]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 对撞指针模板
left, right := 0, len(arr)-1
for left < right {
    if condition(arr[left], arr[right]) {
        // 记录/处理
        left++
        right--
    } else if tooSmall {
        left++
    } else {
        right--
    }
}

// 快慢指针模板（原地去重）
slow := 0
for fast := 0; fast < len(arr); fast++ {
    if arr[fast] != arr[slow] {
        slow++
        arr[slow] = arr[fast]
    }
}

2. 滑动窗口 (Sliding Window)

适用场景：子数组/子串问题，求满足条件的最长/最短窗口。

  • 变长窗口：右指针扩张，不满足时左指针收缩。
  • 定长窗口：窗口大小固定为 k，整体右移。
1
2
3
4
5
6
7
8
9
10
11
# 变长窗口模板（最长满足条件子串）
left = 0
window = {}  # 或用计数器
for right in range(len(s)):
    # 扩张：加入 s[right]
    window[s[right]] = window.get(s[right], 0) + 1
    # 收缩：窗口不合法时移动 left
    while not valid(window):
        window[s[left]] -= 1
        left += 1
    ans = max(ans, right - left + 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 变长窗口模板（最长满足条件子串）
window := map[byte]int{}
left, ans := 0, 0
for right := 0; right < len(s); right++ {
    // 扩张：加入 s[right]
    window[s[right]]++
    // 收缩：窗口不合法时移动 left
    for !valid(window) {
        window[s[left]]--
        left++
    }
    if right-left+1 > ans {
        ans = right - left + 1
    }
}

3. 前缀和 & 差分 (Prefix Sum / Difference Array)

适用场景：

  • 前缀和：O(1) 查询任意区间 [l, r] 的子数组和；结合哈希表找满足条件的子数组。
  • 差分：对区间 [l, r] 整体加减，最后还原原数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 前缀和
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i+1] = prefix[i] + arr[i]
# 区间和 [l, r] = prefix[r+1] - prefix[l]

# 前缀和 + 哈希（子数组和为 k 的个数）
count = {0: 1}
cur = 0
for x in arr:
    cur += x
    ans += count.get(cur - k, 0)
    count[cur] = count.get(cur, 0) + 1

# 差分
diff = [0] * (n + 1)
def add(l, r, val):
    diff[l] += val
    diff[r+1] -= val
# 还原：对 diff 做前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 前缀和
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
    prefix[i+1] = prefix[i] + arr[i]
}
// 区间和 [l, r] = prefix[r+1] - prefix[l]

// 前缀和 + 哈希（子数组和为 k 的个数）
count := map[int]int{0: 1}
cur, ans := 0, 0
for _, x := range arr {
    cur += x
    ans += count[cur-k]
    count[cur]++
}

// 差分
diff := make([]int, n+1)
add := func(l, r, val int) {
    diff[l] += val
    diff[r+1] -= val
}
// 还原：对 diff 做前缀和
_ = add

适用场景：有序序列查找目标；「在某条件下最大/最小值是多少」的答案二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 标准：找目标值
left, right = 0, len(arr) - 1
while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

# 找左边界（第一个 >= target 的位置）
left, right = 0, len(arr)
while left < right:
    mid = (left + right) // 2
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid
return left

# 答案二分模板（最大化最小值 / 最小化最大值）
def feasible(mid) -> bool:
    ...  # 判断 mid 是否可行

left, right = lo, hi
while left < right:
    mid = (left + right) // 2
    if feasible(mid):
        right = mid        # 找最小可行
    else:
        left = mid + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 标准：找目标值
left, right := 0, len(arr)-1
for left <= right {
    mid := (left + right) / 2
    if arr[mid] == target {
        return mid
    } else if arr[mid] < target {
        left = mid + 1
    } else {
        right = mid - 1
    }
}

// 找左边界（第一个 >= target 的位置）
left, right = 0, len(arr)
for left < right {
    mid := (left + right) / 2
    if arr[mid] < target {
        left = mid + 1
    } else {
        right = mid
    }
}
// return left

// 答案二分模板（最大化最小值 / 最小化最大值）
feasible := func(mid int) bool {
    // 判断 mid 是否可行
    return true
}
left, right = lo, hi
for left < right {
    mid := (left + right) / 2
    if feasible(mid) {
        right = mid // 找最小可行
    } else {
        left = mid + 1
    }
}

5. 排序辅助 (Sorting)

适用场景：排序后用双指针/贪心；自定义排序键。

  • 排序消除无序状态，让问题退化为更简单的情形。
  • 常见：合并区间（按起点排序）、三数之和（排序后双指针）。
1
intervals.sort(key=lambda x: x[0])  # 区间按左端点排序
1
2
3
4
5
6
import "sort"

// 区间按左端点排序
sort.Slice(intervals, func(i, j int) bool {
    return intervals[i][0] < intervals[j][0]
})

6. 哈希表 (Hash Map / Set)

适用场景：O(1) 查询/计数/去重；记录已访问状态。

1
2
3
4
5
6
7
8
9
10
# 计数
from collections import Counter
cnt = Counter(arr)

# 两数之和
seen = {}
for i, x in enumerate(arr):
    if target - x in seen:
        return [seen[target - x], i]
    seen[x] = i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 计数
cnt := map[int]int{}
for _, x := range arr {
    cnt[x]++
}

// 两数之和
seen := map[int]int{}
for i, x := range arr {
    if j, ok := seen[target-x]; ok {
        return []int{j, i}
    }
    seen[x] = i
}

7. 栈 (Stack)

适用场景：括号匹配；单调栈处理「下一个更大/更小元素」「柱状图最大矩形」。

1
2
3
4
5
6
7
8
# 单调递减栈（找右边第一个更大的元素）
stack = []
res = [-1] * n
for i in range(n):
    while stack and arr[stack[-1]] < arr[i]:
        idx = stack.pop()
        res[idx] = arr[i]
    stack.append(i)
1
2
3
4
5
6
7
8
9
10
11
12
// 单调递减栈（找右边第一个更大的元素）
stack := []int{}
res := make([]int, n)
for i := range res { res[i] = -1 }
for i := 0; i < n; i++ {
    for len(stack) > 0 && arr[stack[len(stack)-1]] < arr[i] {
        idx := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res[idx] = arr[i]
    }
    stack = append(stack, i)
}

8. 单调队列 (Monotonic Deque)

适用场景：滑动窗口内的最大/最小值（O(n) 解决）。

1
2
3
4
5
6
7
8
9
10
11
12
from collections import deque
dq = deque()  # 存下标，保持单调递减（求最大值）
for i in range(n):
    # 移除超出窗口的元素
    if dq and dq[0] < i - k + 1:
        dq.popleft()
    # 维护单调性（从尾部移除比当前小的）
    while dq and arr[dq[-1]] < arr[i]:
        dq.pop()
    dq.append(i)
    if i >= k - 1:
        ans.append(arr[dq[0]])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 单调队列（滑动窗口最大值）
dq := []int{} // 存下标，单调递减
ans := []int{}
for i := 0; i < n; i++ {
    // 移除超出窗口的元素
    if len(dq) > 0 && dq[0] < i-k+1 {
        dq = dq[1:]
    }
    // 维护单调性（从尾部移除比当前小的）
    for len(dq) > 0 && arr[dq[len(dq)-1]] < arr[i] {
        dq = dq[:len(dq)-1]
    }
    dq = append(dq, i)
    if i >= k-1 {
        ans = append(ans, arr[dq[0]])
    }
}

9. 堆 / 优先队列 (Heap / Priority Queue)

适用场景：TopK 问题；合并 K 个有序链表；动态维护最大/最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq

# 最小堆（Python 默认）
heap = []
heapq.heappush(heap, val)
top = heapq.heappop(heap)

# 最大堆：存负数
heapq.heappush(heap, -val)

# 最小的 K 个数（大根堆维护大小 K 的堆）
heap = []
for x in arr:
    heapq.heappush(heap, -x)
    if len(heap) > k:
        heapq.heappop(heap)

# 合并 K 个有序链表：初始把每个链表头入堆
heapq.heappush(heap, (node.val, i, node))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import "container/heap"

// 最小堆
type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any          { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

// 最大堆：Less 取反
type MaxHeap []int
func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any          { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

// 最小的 K 个数（大根堆维护大小 K）
h := &MaxHeap{}
heap.Init(h)
for _, x := range arr {
    heap.Push(h, x)
    if h.Len() > k {
        heap.Pop(h)
    }
}

10. 树 (Tree)

递归三要素：终止条件 → 本层逻辑 → 返回值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# DFS 后序（常用于"需要子树信息"类题目）
def dfs(node):
    if not node:
        return base_value
    left = dfs(node.left)
    right = dfs(node.right)
    return combine(left, right, node.val)

# BFS 层序遍历
from collections import deque
q = deque([root])
while q:
    level_size = len(q)
    for _ in range(level_size):
        node = q.popleft()
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// DFS 后序（常用于"需要子树信息"类题目）
func dfs(node *TreeNode) int {
    if node == nil {
        return baseValue
    }
    left := dfs(node.Left)
    right := dfs(node.Right)
    return combine(left, right, node.Val)
}

// BFS 层序遍历
queue := []*TreeNode{root}
for len(queue) > 0 {
    levelSize := len(queue)
    for i := 0; i < levelSize; i++ {
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil { queue = append(queue, node.Left) }
        if node.Right != nil { queue = append(queue, node.Right) }
    }
}

常见题型：

  • 路径和类 → DFS 传递路径信息
  • 最近公共祖先 (LCA) → 后序 DFS
  • 序列化/反序列化 → BFS 或 DFS

11. 图 (Graph)

BFS（最短路 / 多源扩散）

1
2
3
4
5
6
7
8
9
from collections import deque
dist = {start: 0}
q = deque([start])
while q:
    node = q.popleft()
    for neighbor in graph[node]:
        if neighbor not in dist:
            dist[neighbor] = dist[node] + 1
            q.append(neighbor)
1
2
3
4
5
6
7
8
9
10
11
12
13
// BFS 最短路
dist := map[int]int{start: 0}
queue := []int{start}
for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    for _, neighbor := range graph[node] {
        if _, visited := dist[neighbor]; !visited {
            dist[neighbor] = dist[node] + 1
            queue = append(queue, neighbor)
        }
    }
}

DFS（连通分量 / 岛屿问题）

1
2
3
4
5
6
visited = set()
def dfs(node):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor)
1
2
3
4
5
6
7
8
9
10
11
// DFS 连通分量
visited := map[int]bool{}
var dfs func(node int)
dfs = func(node int) {
    visited[node] = true
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            dfs(neighbor)
        }
    }
}

拓扑排序（有向无环图 / 依赖关系）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import deque
in_degree = {v: 0 for v in graph}
for u in graph:
    for v in graph[u]:
        in_degree[v] += 1
q = deque([v for v in in_degree if in_degree[v] == 0])
order = []
while q:
    node = q.popleft()
    order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            q.append(neighbor)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 拓扑排序（Kahn 算法）
inDegree := make([]int, n)
for u := 0; u < n; u++ {
    for _, v := range graph[u] {
        inDegree[v]++
    }
}
queue := []int{}
for v, d := range inDegree {
    if d == 0 { queue = append(queue, v) }
}
order := []int{}
for len(queue) > 0 {
    node := queue[0]; queue = queue[1:]
    order = append(order, node)
    for _, neighbor := range graph[node] {
        inDegree[neighbor]--
        if inDegree[neighbor] == 0 {
            queue = append(queue, neighbor)
        }
    }
}

并查集 (Union-Find)

1
2
3
4
5
6
7
parent = list(range(n))
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 路径压缩
    return parent[x]
def union(x, y):
    parent[find(x)] = find(y)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 并查集
parent := make([]int, n)
for i := range parent { parent[i] = i }
var find func(x int) int
find = func(x int) int {
    if parent[x] != x {
        parent[x] = find(parent[x]) // 路径压缩
    }
    return parent[x]
}
union := func(x, y int) {
    parent[find(x)] = find(y)
}
_ = union

12. 动态规划 (Dynamic Programming)

思路：状态定义 → 转移方程 → 初始化 → 遍历顺序。

线性 DP

1
2
3
4
5
6
# 最长递增子序列 (LIS) — O(n²)
dp = [1] * n
for i in range(n):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)
1
2
3
4
5
6
7
8
9
10
// 最长递增子序列 (LIS) — O(n²)
dp := make([]int, n)
for i := range dp { dp[i] = 1 }
for i := 0; i < n; i++ {
    for j := 0; j < i; j++ {
        if arr[j] < arr[i] && dp[j]+1 > dp[i] {
            dp[i] = dp[j] + 1
        }
    }
}

背包 DP

1
2
3
4
5
6
7
8
9
10
# 0-1 背包（逆序遍历容量）
dp = [0] * (W + 1)
for weight, value in items:
    for w in range(W, weight - 1, -1):
        dp[w] = max(dp[w], dp[w - weight] + value)

# 完全背包（正序遍历容量）
for weight, value in items:
    for w in range(weight, W + 1):
        dp[w] = max(dp[w], dp[w - weight] + value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 0-1 背包（逆序遍历容量）
dp := make([]int, W+1)
for _, item := range items {
    weight, value := item[0], item[1]
    for w := W; w >= weight; w-- {
        if dp[w-weight]+value > dp[w] {
            dp[w] = dp[w-weight] + value
        }
    }
}

// 完全背包（正序遍历容量）
for _, item := range items {
    weight, value := item[0], item[1]
    for w := weight; w <= W; w++ {
        if dp[w-weight]+value > dp[w] {
            dp[w] = dp[w-weight] + value
        }
    }
}

区间 DP

1
2
3
4
5
6
7
8
# 戳气球 / 矩阵链乘
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):          # 区间长度从小到大
    for left in range(n - length + 1):
        right = left + length - 1
        for k in range(left, right):    # 枚举分割点
            dp[left][right] = max(dp[left][right],
                                  dp[left][k] + dp[k+1][right] + cost(left, k, right))
1
2
3
4
5
6
7
8
9
10
11
12
// 区间 DP（戳气球 / 矩阵链乘）
dp := make([][]int, n)
for i := range dp { dp[i] = make([]int, n) }
for length := 2; length <= n; length++ {
    for left := 0; left <= n-length; left++ {
        right := left + length - 1
        for k := left; k < right; k++ {
            val := dp[left][k] + dp[k+1][right] + cost(left, k, right)
            if val > dp[left][right] { dp[left][right] = val }
        }
    }
}

状态压缩 DP

1
2
3
4
5
6
7
8
9
10
# 旅行商问题 (TSP)
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0
for mask in range(1 << n):
    for u in range(n):
        if not (mask >> u & 1): continue
        for v in range(n):
            if mask >> v & 1: continue
            dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v],
                                          dp[mask][u] + dist[u][v])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 旅行商问题 (TSP) 状压 DP
const inf = 1<<31 - 1
dp := make([][]int, 1<<n)
for i := range dp {
    dp[i] = make([]int, n)
    for j := range dp[i] { dp[i][j] = inf }
}
dp[1][0] = 0
for mask := 0; mask < (1 << n); mask++ {
    for u := 0; u < n; u++ {
        if mask>>u&1 == 0 || dp[mask][u] == inf { continue }
        for v := 0; v < n; v++ {
            if mask>>v&1 == 1 { continue }
            next := mask | (1 << v)
            if dp[mask][u]+dist[u][v] < dp[next][v] {
                dp[next][v] = dp[mask][u] + dist[u][v]
            }
        }
    }
}

13. 贪心 (Greedy)

适用场景：每步局部最优可以推导全局最优（需证明或凭直觉+反例验证）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 区间调度（最多不重叠区间）
intervals.sort(key=lambda x: x[1])  # 按结束时间排序
end = float('-inf')
count = 0
for s, e in intervals:
    if s >= end:
        count += 1
        end = e

# 跳跃游戏
max_reach = 0
for i in range(n):
    if i > max_reach:
        return False
    max_reach = max(max_reach, i + nums[i])
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import "math"

// 区间调度（最多不重叠区间）
sort.Slice(intervals, func(i, j int) bool {
    return intervals[i][1] < intervals[j][1]
})
end, count := math.MinInt32, 0
for _, iv := range intervals {
    if iv[0] >= end {
        count++
        end = iv[1]
    }
}

// 跳跃游戏
maxReach := 0
for i := 0; i < n; i++ {
    if i > maxReach { return false }
    if i+nums[i] > maxReach { maxReach = i + nums[i] }
}
return true

14. 回溯 (Backtracking)

适用场景：枚举所有可能解——子集、排列、组合、N 皇后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 通用回溯模板
def backtrack(path, choices):
    if 终止条件:
        result.append(path[:])
        return
    for choice in choices:
        # 做选择
        path.append(choice)
        backtrack(path, new_choices)
        # 撤销选择
        path.pop()

# 子集（不含重复元素）
def dfs(start, path):
    res.append(path[:])
    for i in range(start, n):
        path.append(nums[i])
        dfs(i + 1, path)
        path.pop()

# 全排列（含重复时先排序 + used 数组剪枝）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 通用回溯模板（子集）
var res [][]int
var backtrack func(start int, path []int)
backtrack = func(start int, path []int) {
    tmp := make([]int, len(path))
    copy(tmp, path)
    res = append(res, tmp)
    for i := start; i < len(nums); i++ {
        path = append(path, nums[i])
        backtrack(i+1, path)
        path = path[:len(path)-1]
    }
}
backtrack(0, []int{})

// 全排列（used 数组剪枝）
used := make([]bool, len(nums))
var perm func(path []int)
perm = func(path []int) {
    if len(path) == len(nums) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        res = append(res, tmp)
        return
    }
    for i, x := range nums {
        if used[i] { continue }
        used[i] = true
        perm(append(path, x))
        used[i] = false
    }
}

15. 分治 (Divide and Conquer)

适用场景：问题可被拆分为同类子问题；归并排序；快速幂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 归并排序（同时统计逆序对）
def merge_sort(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, cnt1 = merge_sort(arr[:mid])
    right, cnt2 = merge_sort(arr[mid:])
    merged, cnt = [], cnt1 + cnt2
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            cnt += len(left) - i
    merged += left[i:] + right[j:]
    return merged, cnt

# 快速幂
def pow(base, exp, mod):
    res = 1
    while exp:
        if exp & 1:
            res = res * base % mod
        base = base * base % mod
        exp >>= 1
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 归并排序（同时统计逆序对）
func mergeSort(arr []int) ([]int, int) {
    if len(arr) <= 1 { return arr, 0 }
    mid := len(arr) / 2
    left, cnt1 := mergeSort(arr[:mid])
    right, cnt2 := mergeSort(arr[mid:])
    merged := make([]int, 0, len(arr))
    cnt, i, j := cnt1+cnt2, 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            merged = append(merged, left[i]); i++
        } else {
            merged = append(merged, right[j]); j++
            cnt += len(left) - i
        }
    }
    merged = append(merged, left[i:]...)
    merged = append(merged, right[j:]...)
    return merged, cnt
}

// 快速幂
func powMod(base, exp, mod int) int {
    res := 1
    for exp > 0 {
        if exp&1 == 1 { res = res * base % mod }
        base = base * base % mod
        exp >>= 1
    }
    return res
}

16. 字符串 (String)

常见手法：

  • 双指针/滑动窗口：最长无重复子串、最小覆盖子串。
  • 哈希：字母异位词分组（以排序字符串为键）。
  • KMP：O(n) 字符串匹配，构建 next 数组。
1
2
3
4
5
6
7
8
9
10
11
# KMP next 数组
def build_next(pattern):
    next = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = next[j-1]
        if pattern[i] == pattern[j]:
            j += 1
        next[i] = j
    return next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// KMP next 数组
func buildNext(pattern string) []int {
    next := make([]int, len(pattern))
    j := 0
    for i := 1; i < len(pattern); i++ {
        for j > 0 && pattern[i] != pattern[j] {
            j = next[j-1]
        }
        if pattern[i] == pattern[j] {
            j++
        }
        next[i] = j
    }
    return next
}

17. 位运算 (Bit Manipulation)

技巧 表达式 含义
取最低位 1 x & (-x) lowbit，树状数组核心
消最低位 1 x & (x-1) 统计 1 的个数
判断奇偶 x & 1
异或消重 a ^ a = 0 找唯一出现奇数次的数
第 k 位 (x >> k) & 1
枚举子集 for sub in range(mask, -1, -1): sub = (sub-1) & mask 状压 DP 
1
2
3
# 只出现一次的数（其余出现两次）
from functools import reduce
return reduce(lambda a, b: a ^ b, nums)
1
2
3
4
5
6
7
8
9
10
11
// 只出现一次的数（其余出现两次）
result := 0
for _, x := range nums {
    result ^= x
}
return result

// 枚举子集
for sub := mask; sub > 0; sub = (sub - 1) & mask {
    // 处理子集 sub
}

18. 数学 (Math)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 最大公约数
from math import gcd
lcm = a * b // gcd(a, b)

# 质数筛（埃氏筛）
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

# 组合数（杨辉三角）
C = [[0] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    C[i][0] = 1
    for j in range(1, i+1):
        C[i][j] = C[i-1][j-1] + C[i-1][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 最大公约数
func gcd(a, b int) int {
    for b != 0 { a, b = b, a%b }
    return a
}
// lcm := a * b / gcd(a, b)

// 质数筛（埃氏筛）
func sieve(n int) []int {
    isPrime := make([]bool, n+1)
    for i := 2; i <= n; i++ { isPrime[i] = true }
    for i := 2; i*i <= n; i++ {
        if isPrime[i] {
            for j := i * i; j <= n; j += i {
                isPrime[j] = false
            }
        }
    }
    primes := []int{}
    for i := 2; i <= n; i++ {
        if isPrime[i] { primes = append(primes, i) }
    }
    return primes
}

// 组合数（杨辉三角）
C := make([][]int, n+1)
for i := range C {
    C[i] = make([]int, n+1)
    C[i][0] = 1
    for j := 1; j <= i; j++ {
        C[i][j] = C[i-1][j-1] + C[i-1][j]
    }
}

19. 设计题 (Design)

LRU Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()
    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// LRU Cache（双向链表 + 哈希表）
type Node struct { key, val int; prev, next *Node }
type LRUCache struct {
    cap        int
    cache      map[int]*Node
    head, tail *Node
}
func NewLRU(capacity int) LRUCache {
    h, t := &Node{}, &Node{}
    h.next = t; t.prev = h
    return LRUCache{cap: capacity, cache: map[int]*Node{}, head: h, tail: t}
}
func (l *LRUCache) remove(n *Node) {
    n.prev.next = n.next; n.next.prev = n.prev
}
func (l *LRUCache) addToFront(n *Node) {
    n.next = l.head.next; n.prev = l.head
    l.head.next.prev = n; l.head.next = n
}
func (l *LRUCache) Get(key int) int {
    if n, ok := l.cache[key]; ok {
        l.remove(n); l.addToFront(n); return n.val
    }
    return -1
}
func (l *LRUCache) Put(key, value int) {
    if n, ok := l.cache[key]; ok {
        n.val = value; l.remove(n); l.addToFront(n); return
    }
    n := &Node{key: key, val: value}
    l.cache[key] = n; l.addToFront(n)
    if len(l.cache) > l.cap {
        lru := l.tail.prev
        l.remove(lru); delete(l.cache, lru.key)
    }
}

数据流中位数（双堆）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []   # 大根堆（存较小半部分，取负数模拟）
        self.hi = []   # 小根堆（存较大半部分）
    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.lo) < len(self.hi):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
    def findMedian(self):
        if len(self.lo) == len(self.hi):
            return (-self.lo[0] + self.hi[0]) / 2
        return -self.lo[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 数据流中位数（双堆）
import "container/heap"

type MinH []int
func (h MinH) Len() int           { return len(h) }
func (h MinH) Less(i, j int) bool { return h[i] < h[j] }
func (h MinH) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinH) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MinH) Pop() any          { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

type MaxH []int
func (h MaxH) Len() int           { return len(h) }
func (h MaxH) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxH) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxH) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxH) Pop() any          { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

type MedianFinder struct{ lo *MaxH; hi *MinH }
func NewMedianFinder() MedianFinder {
    lo, hi := &MaxH{}, &MinH{}
    heap.Init(lo); heap.Init(hi)
    return MedianFinder{lo, hi}
}
func (m *MedianFinder) AddNum(num int) {
    heap.Push(m.lo, num)
    heap.Push(m.hi, heap.Pop(m.lo))
    if m.lo.Len() < m.hi.Len() {
        heap.Push(m.lo, heap.Pop(m.hi))
    }
}
func (m *MedianFinder) FindMedian() float64 {
    if m.lo.Len() == m.hi.Len() {
        return float64((*m.lo)[0]+(*m.hi)[0]) / 2.0
    }
    return float64((*m.lo)[0])
}

选题思路速查表

题目特征 优先考虑
有序数组，找两个数 双指针
子数组/子串，最长/最短 滑动窗口
区间求和，子数组和 前缀和 + 哈希
有序，找值/边界 二分查找
下一个更大/更小元素 单调栈
滑动窗口内最值 单调队列
TopK / 动态最值 堆
枚举所有可能 回溯
最优子结构，重叠子问题 动态规划
局部最优推全局 贪心
连通性，最短路 图 BFS/DFS
集合合并，判断连通 并查集
出现次数，O(1)查找 哈希表
状态集合（二进制表示） 状压 DP