IA · 算法与数据结构

本区纯内联——算法不属于任何语言域，因此不链 A 前端域，全部解答就在本页。 示例用 TypeScript / JavaScript 书写（前端可直接抄进白板），思路与语言无关。

📌 用法：先做高频 Top 10 自测；每种结构记住"什么时候用 + 复杂度"两件事，比背代码重要。

⚠️ 硬规则回顾：算法（IA）不进 A 前端域。手写题（防抖/深拷贝/Promise 系列）属工程向，见 A18。

---

高频 Top 10（不会的话优先补这些）

#	题目	考点	难度
1	两数之和	哈希换时间	易
2	反转链表	指针操作、迭代 vs 递归	易
3	有效的括号 / 最小栈	栈	易
4	二叉树层序遍历	BFS 队列	易
5	二分查找（含边界变体）	边界不写错	易
6	快排 / 归并	分治、稳定性	中
7	LRU 缓存	哈希 + 双向链表	中
8	TopK（第 K 大）	堆 / 快排分区	中
9	最长无重复子串 / 滑动窗口	双指针	中
10	爬楼梯 / 打家劫舍 / 背包	DP 状态定义	中

---

一、先建立判断框架（比刷题重要）

1.1 复杂度速查

结构	访问	查找	插入	删除	备注
数组	O(1)	O(n)	O(n)	O(n)	内存连续，缓存友好
链表	O(n)	O(n)	O(1)*	O(1)*	*已知前驱节点时
哈希表	—	O(1)	O(1)	O(1)	均摊，冲突退化 O(n)
栈 / 队列	—	O(n)	O(1)	O(1)	队尾/栈顶
二叉搜索树	—	O(log n)	O(log n)	O(log n)	退化成链则 O(n)，故用平衡树
堆	—	O(n)	O(log n)	O(log n)	取最值 O(1)

常见排序：

排序	平均	最坏	空间	稳定	前端备注
快排	O(n log n)	O(n²)	O(log n)	✗	Array.sort 在 V8 中是 TimSort（稳定）
归并	O(n log n)	O(n log n)	O(n)	✓	适合外排、链表排序
堆排	O(n log n)	O(n log n)	O(1)	✗	TopK 首选
计数/桶	O(n + k)	O(n + k)	O(k)	✓	值域小才用

⚠️ 别口嗨"Array.sort 是快排"——V8 7.0 起用 TimSort（归并 + 插入混合），稳定，且对小数组用插入排序。

1.2 看到题目怎么选（决策树）

需要"查某个东西在不在 / 出现次数"      → 哈希 Set / Map
需要"上一个/下一个、配对、回退"        → 栈
需要"按顺序处理、层序"                → 队列 (BFS)
数组有序 && 找某个值/边界              → 二分
求"最大/最小/第 K 个"                 → 堆
连续子串/子数组 && 有单调性            → 双指针 / 滑动窗口
求"所有方案 / 能不能到达"             → DFS 回溯 / BFS
求"最优解" && 有重叠子问题            → DP
图里最短路径（无权）                  → BFS；（带权）→ Dijkstra
"最近一段时间内的最值"                → 单调栈 / 单调队列

---

二、数组与字符串

Q：两数之和（内联）

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>()   // 值 → 下标
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need)!, i]
    seen.set(nums[i], i)                   // 先查后存，避免自己和自己配对
  }
  return []
}

暴力 O(n²) → 哈希换空间 O(n)。关键：先查后存。

Q：无重复字符的最长子串（滑动窗口模板）

function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>()   // 字符 → 最近下标
  let left = 0, best = 0
  for (let right = 0; right < s.length; right++) {
    const c = s[right]
    if (last.has(c) && last.get(c)! >= left) left = last.get(c)! + 1  // 收缩左边界
    last.set(c, right)
    best = Math.max(best, right - left + 1)
  }
  return best
}

滑动窗口通用骨架：right 扩张 → 更新状态 → while (不满足条件) left 收缩 → 更新答案。

Q：二分查找的边界怎么不写错？

记住一套模板（左闭右开 [lo, hi)）：

function lowerBound(a: number[], target: number): number {  // 第一个 >= target 的位置
  let lo = 0, hi = a.length        // 注意 hi 是 length，不是 length-1
  while (lo < hi) {                // 无等号
    const mid = lo + ((hi - lo) >> 1)
    if (a[mid] < target) lo = mid + 1
    else hi = mid
  }
  return lo
}

三个变体只改一处判断：< target → 第一个 ≥；<= target → 第一个 >；找"最后一个 ≤"则先求第一个 > 再减 1。 死循环的根因是 mid 取值与边界收缩不匹配，用左闭右开可以从根上避免。

---

三、链表

Q：反转链表（迭代 + 递归）

// 迭代：三指针，pre / cur / next 依次前移
function reverseList(head: ListNode | null): ListNode | null {
  let pre: ListNode | null = null, cur = head
  while (cur) {
    const next = cur.next
    cur.next = pre
    pre = cur
    cur = next
  }
  return pre                        // pre 最终指向原尾节点
}

// 递归：假设后面的都反转好了，只需把当前节点接到尾部
function reverseListRec(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head
  const newHead = reverseListRec(head.next)
  head.next.next = head             // 让后一个节点指回自己
  head.next = null                  // 断开自己原来的指向，防成环
  return newHead
}

Q：判断链表有环 + 找入环点（Floyd 快慢指针）

function detectCycle(head: ListNode | null): ListNode | null {
  let slow = head, fast = head
  while (fast?.next) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) {            // 相遇即有环
      let p = head
      while (p !== slow) { p = p!.next; slow = slow!.next }  // 一从头、一从相遇点同速走
      return p                      // 再次相遇处即入环点
    }
  }
  return null
}

为什么再走一次能找到入环点：设头到入环 a、环长 b，相遇时 fast = 2·slow，可推得从头走到入环的距离 = 从相遇点再走 a 步。

Q：合并两个有序链表——用哑节点（dummy head）省掉头节点的特判，这是所有链表题的通用技巧。

---

四、栈与队列

Q：用栈实现队列 / 用队列实现栈

• 栈实现队列：两个栈，in 只进、out 只出；out 空时把 in 全部倒过去（均摊 O(1)）。
• 队列实现栈：一个队列，每次入队后把前面所有元素依次挪到队尾（入队 O(n)，出队 O(1)）。

Q：最小栈（Min Stack）

class MinStack {
  private data: number[] = []
  private mins: number[] = []        // 辅助栈：只存"当前最小值"
  push(x: number) {
    this.data.push(x)
    const cur = this.mins.length ? this.mins[this.mins.length - 1] : Infinity
    this.mins.push(Math.min(cur, x)) // 存的是"到这里为止的最小值"，不是"比当前小的"
  }
  pop() { this.mins.pop(); return this.data.pop() }
  getMin() { return this.mins[this.mins.length - 1] }
}

易错点：辅助栈存"当前最小值"而非"只存更小的"，这样 pop 才能同步弹出，不会漏。

Q：单调栈解决什么问题？

求"左边/右边第一个比它大/小的元素"、每日温度、柱状图最大矩形、接雨水。 核心：栈内保持单调，遇到破坏单调性的元素就弹栈并结算，每个元素入栈一次、出栈一次 → O(n)。

// 每日温度：还要等几天才有更暖的天
function dailyTemperatures(t: number[]): number[] {
  const ans = new Array(t.length).fill(0)
  const st: number[] = []                     // 单调递减栈，存下标
  for (let i = 0; i < t.length; i++) {
    while (st.length && t[i] > t[st[st.length - 1]]) {
      const j = st.pop()!
      ans[j] = i - j                          // 当前 i 就是 j 右边第一个更大的
    }
    st.push(i)
  }
  return ans
}

---

五、树

Q：三种遍历怎么写（递归 + 迭代）

递归一行改顺序即可（前序：根左右；中序：左根右；后序：左右根）。 面试常要求写迭代：

// 前序（根左右）：栈 + 先压右再压左
function preorder(root: TreeNode | null): number[] {
  if (!root) return []
  const out: number[] = [], st: TreeNode[] = [root]
  while (st.length) {
    const n = st.pop()!
    out.push(n.val)
    if (n.right) st.push(n.right)   // 栈是 LIFO，所以右孩子先入才能后出
    if (n.left) st.push(n.left)
  }
  return out
}

// 层序（BFS）：队列，按层处理
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return []
  const res: number[][] = [], q: TreeNode[] = [root]
  while (q.length) {
    const size = q.length            // 关键：先固定本层长度，再整层弹出
    const level: number[] = []
    for (let i = 0; i < size; i++) {
      const n = q.shift()!
      level.push(n.val)
      if (n.left) q.push(n.left)
      if (n.right) q.push(n.right)
    }
    res.push(level)
  }
  return res
}

⚠️ 白板里别用 Array.prototype.shift() 当队列（O(n)），用双指针 + 数组或 head 索引模拟。

Q：二叉搜索树（BST）为什么重要？

中序遍历 BST = 升序序列——这条性质能秒掉"第 K 小""验证 BST"" BST 转累加树"一整类题。 代价：插入顺序不当会退化成链表（O(n)），所以工程上用红黑树（Java TreeMap）/ 跳表（Redis ZSet）。

Q：回溯的通用骨架

function backtrack(path: T[], choices: T[], start: number) {
  if (满足结束条件) { res.push([...path]); return }   // 必须拷贝
  for (let i = start; i < choices.length; i++) {
    if (需要剪枝) continue
    path.push(choices[i])           // 做选择
    backtrack(path, choices, i + 1) // 递归（i 或 i+1 决定能否重复使用）
    path.pop()                      // 撤销选择——最容易漏的一行
  }
}

三要素：路径（已选）、选择列表（可选）、结束条件。剪枝是优化，去重常靠排序 + i > start && a[i] === a[i-1] → continue。

---

六、堆与 TopK

Q：TopK 为什么用堆而不用排序？

全排序 O(n log n)，堆只用维护 K 个元素 → O(n log K)，且内存 O(K)。 n 很大（10 亿）、K 很小（100）时差距是决定性的——这就是"内存里放不下"场景的标准答案。

// 第 K 大：维护一个大小为 K 的小顶堆，堆顶就是第 K 大
class MinHeap {
  private a: number[] = []
  get size() { return this.a.length }
  peek() { return this.a[0] }
  push(x: number) {
    this.a.push(x); this.up(this.a.length - 1)
  }
  pop() {
    const top = this.a[0], last = this.a.pop()!
    if (this.a.length) { this.a[0] = last; this.down(0) }
    return top
  }
  private up(i: number) {
    while (i > 0) {
      const p = (i - 1) >> 1
      if (this.a[p] <= this.a[i]) break
      ;[this.a[p], this.a[i]] = [this.a[i], this.a[p]]; i = p
    }
  }
  private down(i: number) {
    const n = this.a.length
    while (true) {
      let m = i, l = 2 * i + 1, r = l + 1
      if (l < n && this.a[l] < this.a[m]) m = l
      if (r < n && this.a[r] < this.a[m]) m = r
      if (m === i) break
      ;[this.a[m], this.a[i]] = [this.a[i], this.a[m]]; i = m
    }
  }
}

function findKthLargest(nums: number[], k: number): number {
  const h = new MinHeap()
  for (const x of nums) {
    if (h.size < k) h.push(x)
    else if (x > h.peek()) { h.pop(); h.push(x) }   // 比第 K 大还大才替换
  }
  return h.peek()
}

追问："如果 K 很小但 n 极大且数据分布未知？"→ 也可以快排分区（quickselect），平均 O(n)，但最坏 O(n²) 且需要随机化 pivot。

---

七、哈希设计题：LRU 缓存

Q：手写 LRU（Least Recently Used）（最高频的设计题）

要求：get 与 put 都是 O(1)。

思路：哈希表保证 O(1) 查找，双向链表保证 O(1) 移动与删除。 链表按"最近使用"排序——头部最新、尾部最旧，淘汰时删尾节点。

class LRUCache {
  private cap: number
  private map = new Map<number, number>()   // key → value

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

  get(key: number): number {
    if (!this.map.has(key)) return -1
    const v = this.map.get(key)!
    this.map.delete(key)                    // 先删，再重新 set → 排到 Map 末尾（最新）
    this.map.set(key, v)
    return v
  }

  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.cap) {
      this.map.delete(this.map.keys().next().value!)  // 删头部 = 最久未用
    }
  }
}

为什么 JS 的 Map 就够了：Map 保持插入顺序，且 delete + set 等价于"移到最新"， keys().next() 取到的就是最旧的一个。所以 JS 里不需要真的写双向链表——但面试要主动说出这一点， 并说明"在 Java/Go 里 Map 无序，必须自己维护双向链表"。这是加分项。

追问清单：

追问	回答要点
为什么不用数组？	indexOf + splice 是 O(n)
为什么双向链表而不是单向？	删除任意节点需要前驱指针，单链表要 O(n) 找前驱
为什么用哑节点（dummy head/tail）？	省掉"删的是头/尾"的特判
并发环境下怎么办？	加锁或分段锁；Redis 里近似 LRU 靠随机采样
真实工程为什么少用严格 LRU？	维护成本高、对偶发批量扫描不友好 → 常用 LRU-K / LFU / FIFO + TTL

前端关联：图片/组件缓存、路由 KeepAlive 的淘汰、TanStack Query 的 gcTime 缓存回收——都是 LRU 思想。

---

八、排序与分治

Q：手写快排（注意别写退化版）

function quickSort(a: number[], lo = 0, hi = a.length - 1): number[] {
  if (lo >= hi) return a
  const p = partition(a, lo, hi)
  quickSort(a, lo, p - 1)
  quickSort(a, p + 1, hi)
  return a
}
function partition(a: number[], lo: number, hi: number): number {
  const pivot = a[lo + ((hi - lo) >> 1)]   // 取中点，缓解有序数组退化
  let i = lo, j = hi
  while (i <= j) {
    while (a[i] < pivot) i++
    while (a[j] > pivot) j--
    if (i <= j) { [a[i], a[j]] = [a[j], a[i]]; i++; j-- }
  }
  return i
}

三个必答的追问：

1. 什么时候退化 O(n²)？—— 每次 pivot 都取到最值（已排序数组取首元素）。解法：随机 / 三点取中。
2. 为什么不稳定？—— 交换会跨距离移动相同元素。
3. 工程上为什么不用纯快排？—— 递归深度、小数组开销，所以有内省排序 / TimSort（小数组切插入排序）。

Q：归并排序为什么能用来做"链表排序"和"求逆序对"？

归并的合并步骤是 O(n) 且稳定、对链表是 O(1) 额外空间（只改指针），所以链表排序首选归并； 合并时"左边元素 > 右边元素"的次数即逆序对数量——顺带就解了。

---

九、动态规划（DP）

Q：DP 的思考顺序是什么？

按这五步走，绝大多数题都能推出来：

① 定义 dp[i]（或 dp[i][j]）的含义      ← 最难也最关键的一步
② 推导状态转移方程
③ 确定 base case
④ 确定遍历顺序（依赖的方向）
⑤ （可选）空间压缩：只依赖前一行/前一格就降维

Q：爬楼梯 / 打家劫舍 / 最长递增子序列

// 爬楼梯：dp[i] = 到第 i 阶的方法数 = dp[i-1] + dp[i-2]
// 打家劫舍：dp[i] = max(偷这间 dp[i-2] + nums[i], 不偷 dp[i-1])
// 二者都可压成 O(1) 空间，因为只依赖前两格

// 最长递增子序列 LIS：O(n log n) 贪心 + 二分
function lengthOfLIS(nums: number[]): number {
  const tails: number[] = []                 // tails[i] = 长度 i+1 的递增子序列的最小结尾
  for (const x of nums) {
    let lo = 0, hi = tails.length
    while (lo < hi) {                        // 第一个 >= x 的位置
      const mid = lo + ((hi - lo) >> 1)
      if (tails[mid] < x) lo = mid + 1; else hi = mid
    }
    if (lo === tails.length) tails.push(x)
    else tails[lo] = x                       // 替换：让同样长度的结尾尽可能小
  }
  return tails.length
}

⚠️ tails 不是 LIS 本身，只有长度是对的——这是高频追问。

Q：0-1 背包 vs 完全背包

	每个物品	容量遍历方向	组合数内层
0-1 背包	只能用一次	倒序（防重复使用）	—
完全背包	无限次	正序	—
组合（顺序无关，如凑零钱）	—	—	先遍历物品，再遍历容量
排列（顺序有关）	—	—	先遍历容量，再遍历物品

为什么倒序：一维数组下，dp[j - w] 若在本轮已被更新（正序），就变成了"同一个物品用了多次"。

---

十、图

问题	算法	复杂度
无权最短路径	BFS	O(V + E)
带权非负最短路	Dijkstra（优先队列）	O((V+E) log V)
有负权边	Bellman-Ford / SPFA	O(VE)
拓扑排序	入度为 0 入队（Kahn）	O(V + E)
连通分量	并查集 / DFS	≈ O(V + E)

前端真实关联：依赖图分析（构建工具/循环依赖检测 → 拓扑排序）、权限继承、路由可达性、DOM 树的遍历——图的题常包装成"依赖关系"来考。

Q：并查集（Union-Find）解决什么问题？

动态连通性："这两个节点是否在同一集合 + 合并两个集合"，近乎 O(1)。 两个优化缺一不可：路径压缩（find 时把节点直接挂到根）+ 按秩/大小合并。

---

十一、前缀和与差分

• 前缀和：把"区间求和"从 O(n) 降到 O(1)，代价 O(n) 预处理。适合查询多、修改少。
• 差分数组：适合"区间批量加、最后一次性求结果"，区间加从 O(n) 降到 O(1)。
• 二维前缀和：s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]，子矩阵和一次算完。

前端关联：虚拟列表的累计高度缓存、时间轴上的区间统计，本质都是前缀和。

---

十二、面试现场的策略（很加分）

① 先复述题目 + 确认输入边界（空数组？负数？重复？）   ← 面试官在观察这一步
② 先说暴力解和它的复杂度，再说"瓶颈在哪"
③ 提出优化方向，边写边说思路
④ 写完主动走一个用例（含边界）
⑤ 主动报复杂度，并说"如果要进一步优化，可以……"

不会做时怎么办：先给暴力解 → 说出卡在哪 → 提出可能的优化方向（哪怕不完整）。 面试官看的是拆解过程，不是你背没背过这道题。

---

自检清单

• [ ] 复杂度表能默写，且能解释"为什么 V8 的 sort 是稳定排序"
• [ ] 二分能一次写对边界，说清左闭右开为什么不会死循环
• [ ] 反转链表、有环检测（含入环点推导）能白板写出
• [ ] 单调栈知道解决的是"下一个更大/更小"这一类问题
• [ ] 层序遍历会用"先固定 size"处理分层
• [ ] 回溯三要素能说清，pop() 不会漏
• [ ] LRU 能 15 分钟内写完整（Map 或哈希 + 双向链表两种都要会）
• [ ] TopK 能说出"n 很大 K 很小时为什么用堆"
• [ ] DP 五步法能独立推出爬楼梯/打家劫舍/LIS/0-1 背包
• [ ] 快排退化原因与工程化改进（随机 pivot / 小数组插入排序）能讲清楚

相关文档

• I00 · 面试题总览 —— 全部分类
• IX · 综合场景题 —— 系统设计（算法之外的高级岗主战场）
• A18 · 手写题与代码设计 —— 工程向手写（防抖/深拷贝/并发池/LRU 的 JS 实现版）
• A09 · JavaScript 运行时 —— 事件循环输出题（前端特有的"算法题"）