面试算法常见及经典题总结

适用对象：Android / 客户端 / 后端社招与校招，面试环节有手写代码或算法笔试的候选人。
核心目标：不靠题海死记，而是掌握 题型识别 → 解题模板 → 举一反三 的迁移能力。

一、面试算法考什么

1.1 常见考察形式

1.2 面试官真正想看什么

1. 能不能把题翻译成算法模型（排序？双指针？DP？）
2. 能不能分析时间空间复杂度
3. 能不能处理边界（空、单元素、重复、溢出）
4. 能不能在提示下优化（O(n²) → O(n)）
5. 代码是否可维护（不过度炫技）

1.3 备考策略

不要：按题号刷 500 道，做完就忘
要做：
  1. 掌握 12～15 个核心模式（本文第二节）
  2. 每个模式精做 3～5 道经典题
  3. 每道题总结「识别信号 + 模板 + 变体」
  4. 二刷时遮住答案，15 分钟内独立完成

二、题型识别总表（先认模式，再套模板）

三、模式详解 + 经典题 + 举一反三

模式 1：哈希表（HashMap / HashSet）

核心思想

用 O(1) 查找 把「枚举配对」变成「一次遍历」。

经典题 1：两数之和（LeetCode 1）

题意：数组 nums、目标 target，找两数下标使和为 target。

思路

遍历 nums[i]：
  需要 complement = target - nums[i]
  若 map 里已有 complement → 返回答案
  否则 map[nums[i]] = i

复杂度：O(n) 时间，O(n) 空间。

代码骨架（Kotlin）

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    nums.forEachIndexed { i, v ->
        val need = target - v
        map[need]?.let { return intArrayOf(it, i) }
        map[v] = i
    }
    return intArrayOf()
}

举一反三

迁移口诀：

需要「有没有凑成 X」→ 先想哈希；需要「连续子数组和」→ 前缀和 + 哈希。

模式 2：双指针

核心思想

两个下标协同移动，把 O(n²) 枚举降为 O(n)。

子类型

经典题 2：盛最多水的容器（11）

思路

left = 0, right = n - 1
面积 = min(height[left], height[right]) * (right - left)
每次移动较短的那一侧（因为宽度一定变小，只有抬高短板才可能更大）

经典题 3：删除有序数组中的重复项（26）

思路：slow 指向已去重区间末尾，fast 扫描；不同则 slow++ 并赋值。

举一反三

迁移口诀：

有序 + 配对 → 对撞；链表 + 位置/环 → 快慢；原地修改数组 → slow/fast 同向。

模式 3：滑动窗口

核心思想

维护区间 [left, right]，右扩左缩，使窗口满足（或恰好不满足）某条件。

模板

left = 0
for right in 0..n-1:
    将 nums[right] 纳入窗口（更新 count / sum）
    while 窗口不满足条件:
        将 nums[left] 移出窗口
        left++
    更新答案（最长 / 最短 / 计数）

经典题 4：无重复字符的最长子串（3）

思路：HashMap 记字符最后出现下标；若重复且在下标 ≥ left，则 left = last + 1。

经典题 5：最小覆盖子串（76）

思路：need / window 两个 Map；valid 计数；右扩直到满足，再左缩取最短。

举一反三

迁移口诀：

「连续子串 / 子数组」+ 最长/最短/满足条件 → 滑动窗口；固定长度窗口 → 右扩时同步左移。

模式 4：二分查找

核心思想

答案空间或数组具有 单调性，每次排除一半。

两种写法

经典题 6：搜索旋转排序数组（33）

思路：nums[mid] 与 nums[left] 比，判断哪半边有序，再判断 target 是否在有序半边。

经典题 7：在排序数组中查找元素的第一个和最后一个位置（34）

思路：两次二分，分别找左边界和右边界。

举一反三

迁移口诀：

「最小化最大值 / 最大化最小值」→ 二分答案 + check 函数；有序或旋转有序 → 二分下标。

模式 5：链表

必背操作

• 虚拟头节点 dummy：简化头删、合并
• 反转：prev / curr / next 三指针
• 快慢指针：中点、环、倒数第 K

经典题 8：反转链表（206）

fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var curr = head
    while (curr != null) {
        val next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

经典题 9：合并两个有序链表（21）

思路：dummy 尾插，较小者接上；最后接上剩余段。

经典题 10：环形链表 II（142）

思路：快慢相遇后，slow 从头、fast 从相遇点同步走，相遇即环入口（距离关系推导）。

举一反三

迁移口诀：

链表题先想 dummy；要改指向先保存 next；环/中点/倒数 → 快慢指针。

模式 6：栈与单调栈

核心思想

• 栈：最近匹配、逆序处理、DFS 迭代
• 单调栈：每个元素左右第一个更大/更小，O(n)

经典题 11：有效的括号（20）

思路：遇左括号入栈；遇右括号检查栈顶匹配。

经典题 12：每日温度（739）

思路：单调递减栈存下标；当前温度大于栈顶对应温度时弹出并算天数差。

经典题 13：柱状图中最大的矩形（84）

思路：单调递增栈；弹出时以弹出高度为高，宽度由当前 i 与栈顶下标算。

举一反三

迁移口诀：

「下一个更大/更小」→ 单调栈；嵌套结构 → 栈存状态。

模式 7：二叉树 DFS / BFS

DFS 模板（递归）

fun dfs(node: TreeNode?, ...) {
    if (node == null) return
    // 前序位置
    dfs(node.left, ...)
    // 中序位置
    dfs(node.right, ...)
    // 后序位置
}

BFS 模板（层序）

val queue = ArrayDeque<TreeNode>()
queue.add(root)
while (queue.isNotEmpty()) {
    val size = queue.size
    repeat(size) {
        val node = queue.removeFirst()
        // 处理 node
        node.left?.let { queue.add(it) }
        node.right?.let { queue.add(it) }
    }
}

经典题 14：二叉树的最大深度（104）

思路：1 + max(dfs(left), dfs(right))，后序位置聚合。

经典题 15：二叉树的最近公共祖先（236）

思路：后序；若 root 为 p 或 q 返回 root；左右都非空则 root 为 LCA。

经典题 16：二叉树层序遍历（102）

思路：BFS 按层 size 批量出队。

举一反三

迁移口诀：

自底向上聚合 → 后序；路径问题 → 前序 + 回溯；按层 → BFS；BST → 中序或区间约束。

模式 8：回溯（Backtracking）

核心思想

DFS + 显式撤销选择，枚举所有合法方案。

模板

fun backtrack(path: MutableList<Int>, ...) {
    if (满足结束条件) {
        ans.add(path.toList())
        return
    }
    for (选择 in 选择列表) {
        if (剪枝) continue
        做选择
        backtrack(path, ...)
        撤销选择
    }
}

经典题 17：全排列（46）

思路：used 数组标记；每层选一个未使用的数。

经典题 18：子集（78）

思路：每个位置选或不选；或起点 start 递增选，避免重复。

经典题 19：组合总和（39）

思路：可重复选 → 递归时 start 从当前 i 开始，不回头。

举一反三

迁移口诀：

「所有方案」→ 回溯；有重复元素 → 排序 + 同层去重；可重复选 → start 不从 0 重开。

模式 9：动态规划（DP）

识别条件

1. 最优子结构
2. 重叠子问题（记忆化或表格）
3. 能写出状态转移方程

DP 解题四步

1. 定义状态 dp[i] / dp[i][j] 表示什么
2. 转移方程
3. 初始条件
4. 遍历顺序（保证依赖已计算）

经典题 20：爬楼梯（70）

dp[i] = dp[i-1] + dp[i-2]，可压缩为两个变量。

经典题 21：最长递增子序列（300）

dp[i] = 以 i 结尾的 LIS 长度；内层 j < i 且 nums[j] < nums[i] 转移。
优化：耐心排序 + 二分 → O(n log n)。

经典题 22：零钱兑换（322）

dp[amount] = 凑 amount 最少硬币数；完全背包正向遍历。

经典题 23：最长公共子序列（1143）

if (s1[i]==s2[j]) dp[i][j] = dp[i-1][j-1] + 1
else dp[i][j] = max(dp[i-1][j], dp[i][j-1])

经典题 24：编辑距离（72）

增删改三种操作，dp[i][j] 为 s1[0..i) 到 s2[0..j) 最小编辑次数。

DP 子类与举一反三

迁移口诀：

方案数 → 加法转移；最值 → min/max；能否达到 → boolean；二维串 → 双串 DP；选或不选 → 背包。

模式 10：贪心

核心思想

每步做局部最优，需证明能推出全局最优（面试可说「交换论证」思路）。

经典题 25：跳跃游戏（55）

思路：维护能到达的最远位置 maxReach，遍历中若 i > maxReach 失败。

经典题 26：无重叠区间（435）

思路：按区间右端点排序，贪心选结束最早的，能留最多区间。

经典题 27：分发饼干（455）

思路：排序后双指针，小饼干满足小孩子。

举一反三

模式 11：堆（优先队列）

核心思想

动态维护 TopK 或当前最值，插入删除 O(log n)。

经典题 28：数组中的第 K 个最大元素（215）

思路：大小为 K 的小顶堆；或快速选择 O(n) 平均。

经典题 29：合并 K 个升序链表（23）

思路：小顶堆存各链表头节点，每次弹出最小接上。

经典题 30：数据流的中位数（295）

思路：大顶堆存较小一半，小顶堆存较大一半，保持平衡。

举一反三

模式 12：并查集（Union-Find）

模板

class UnionFind(n: Int) {
    private val parent = IntArray(n) { it }
    private val rank = IntArray(n)

    fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])
        return parent[x]
    }

    fun union(a: Int, b: Int): Boolean {
        val ra = find(a)
        val rb = find(b)
        if (ra == rb) return false
        if (rank[ra] < rank[rb]) parent[ra] = rb
        else {
            parent[rb] = ra
            if (rank[ra] == rank[rb]) rank[ra]++
        }
        return true
    }
}

经典题 31：省份数量（547）

思路：邻接矩阵，遍历 union(i,j)，数根节点个数。

经典题 32：冗余连接（684）

思路：加边时若两端已连通则该边冗余。

举一反三

模式 13：图 BFS / DFS

经典题 33：岛屿数量（200）

思路：遍历网格，'1' 则 dfs 沉岛（标记 visited）并 count++。

经典题 34：课程表（207）

思路：拓扑排序，BFS 入度为 0 或 DFS 三色标记判环。

举一反三

模式 14：位运算

常用技巧

经典题 35：只出现一次的数字（136）

思路：全体异或。

经典题 36：位 1 的个数（191）

思路：n & (n-1) 直到为 0。

举一反三

四、经典必刷题单（按优先级）

4.1 第一梯队：必须熟练（各模式代表）

4.2 第二梯队：高频加深

4.3 第三梯队：架构 / 高级岗位加分

五、举一反三方法论（如何从一题扩展到一类）

5.1 四步迁移法

1. 抽象原题：我在「枚举什么」？瓶颈是什么？
2. 识别结构：有序？连续？树？选或不选？
3. 换约束：个数变 K、重复变不可重复、最大变最小
4. 换数据结构：哈希 → 排序双指针；DFS → BFS；数组 → 树

5.2 经典迁移链（建议整链练习）

链 A：两数之和 → 三数之和 → 四数之和 → 最接近的三数之和

哈希 O(n)     →  排序+双指针 O(n²)  →  多一层循环  →  维护最小差值

链 B：爬楼梯 → 打家劫舍 → 打家劫舍 II（环）→ 打家劫舍 III（树）

线性递推  →  不能相邻  →  首尾特殊  →  树形返回双状态

链 C：子集 → 组合 → 排列 → 含重复元素的去重

start 递增  →  固定长度  →  used 标记  →  排序+同层剪枝

链 D：最大子数组和 → 乘积最大子数组 → 环形子数组和

Kadane  →  维护 min/max 乘积  →  总和减最小子数组和

链 E：反转链表 → K 组翻转 → 重排链表 → 合并 K 链表

单组反转  →  分段  →  找中点+反转+合并  →  堆优化

5.3 面试官追问时的升级路径

六、复杂度速查

空间复杂度常见来源：哈希 O(n)、递归栈 O(h)、BFS 队列 O(w)、DP 表 O(n) 或 O(n²)。

七、手写代码注意事项

7.1 边界清单（写完必查）

□ 空输入：null、[]、"" 
□ 单元素
□ 两元素极端
□ 重复元素
□ 整数溢出（Kotlin 一般无此问题，Java 需注意）
□ 链表：空、单节点、环
□ 树：空树、单支、只有左/右

7.2 面试沟通模板

1. 复述题意 + 确认输入输出与约束
2. 举例：正常 case + 边界 case
3. 暴力思路 → 瓶颈 → 优化思路
4. 写代码（主逻辑优先，边界可后补）
5. 口述复杂度
6. 主动提测试用例走一遍

7.3 Android 面试常见语言

• Kotlin：社招 Android 越来越多，本文代码以 Kotlin 为例
• Java：老牌大厂笔试仍常见，语法与 Kotlin 思路一致
• 建议：同一模板用一门语言练熟，另一门能看懂即可

八、八周刷题计划

第 1～2 周：基础模式

第 3～4 周：链表 + 栈 + 二分

第 5～6 周：树 + 回溯

第 7～8 周：DP + 贪心 + 综合

九、设计类常考题

9.1 LRU 缓存（146）

思路：HashMap<key, Node> + 双向链表；get/put 时把节点移到头部；超容量删尾部。

举一反三：LFU 缓存（460）→ 多一个频次维度 + 每层双向链表。

9.2 Min Stack（155）

思路：数据栈 + 辅助栈同步压入当前最小值。

9.3 实现 Trie（208）

思路：子节点数组/Map，isEnd 标记；前缀树支撑自动补全、单词搜索 II。

十、与 Android 开发的联系（面试加分表述）

能在答完题后补一句工程关联，会体现 学以致用，尤其适合 Android 架构岗。

十一、最终应达到的水平

合格的面试算法能力：

• 见到 medium 题 10～15 分钟内 说出正确模式
• 第一梯队 20 题 能独立手写无重大 bug
• 能口述 时间空间复杂度 并给出优化方向
• 能 举一反三：同类变体换约束后知道改哪里
• 代码 边界完整，沟通清晰

十二、最短路径

1. 背熟第二节「题型识别总表」
2. 精做第三节每个模式的「经典题 1」
3. 按第四节第一梯队 20 题过关
4. 每题写三行：识别信号 / 模板 / 一个变体
5. 第八节八周计划或考前集中二刷

一句话总结：

面试算法不是背 500 道题，而是掌握 十几种模式 + 经典题锚点 + 举一反三的迁移链。

附录：LeetCode 题号速查索引