算法面试完全指南
基于《代码随想录——跟着Carl学算法》的知识体系梳理面试高频考点与方法论。
⏱️ 时间复杂度与空间复杂度
什么是时间复杂度
时间复杂度是一个函数，定性描述算法的运行时间。假设数据规模为 n，操作单元数量用 f(n) 表示，随 n 增大执行时间的增长率和 f(n) 相同，记为 O(f(n))。
常见复杂度排行
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)。注意不是越低越好：当 n 很小时，O(5n²) 可能比 O(100n) 更快。
递归算法分析
递归算法的时间复杂度取决于递归的次数与每次递归中操作次数的乘积。以"求 x 的 n 次方"为例，用满二叉树分析：递归 n 次，节点数 2ⁿ-1，时间复杂度 O(n)。
📊 数组
理论基础
数组是存放在连续内存空间上的相同类型数据的集合。下标从 0 开始，内存空间地址连续，因此增删元素时需要移动其他元素。
核心技巧
二分查找、双指针法（快慢指针）、滑动窗口、模拟行为（循环不变量）
经典题目
704.二分查找、27.移除元素、209.长度最小的子数组、59.螺旋矩阵II
易错点
使用 vector.insert() 本身是 O(n) 操作，若在循环中调用，整体复杂度变为 O(n²)。双指针法从后向前遍历可实现 O(n)。
🔗 链表
理论基础
链表通过指针串联，每个节点由数据域和指针域组成。类型包括单链表、双链表、循环链表。长度动态可变，适合频繁增删。
核心技巧
虚拟头节点（dummy head）统一增删操作；双指针法解决环形链表；递归反转链表。
经典题目
203.移除链表元素、206.反转链表、24.两两交换节点、19.删除倒数第N个节点、142.环形链表II
🔍 哈希表
理论基础
根据关键码（key）直接访问数据。用于快速判断元素是否在集合中。C++ 中 unordered_set 和 unordered_map 底层为哈希表，增删查 O(1)。
经典题目
242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和、454.四数相加II
📝 字符串
核心技巧
双指针法、KMP 算法（前缀表）、反转字符串的多种变形。
KMP 关键
前缀表记录了模式串与主串不匹配时，模式串应从哪里重新匹配，避免从头匹配。
经典题目
344.反转字符串、541.反转字符串II、151.反转单词、28.实现 strStr()（KMP）
🗂️ 栈与队列
理论基础
栈是先进后出（FILO），队列是先进先出（FIFO）。
栈的妙用
括号匹配、表达式求值、逆波兰表达式、单调栈解决"下一个更大元素"问题。
队列的妙用
层序遍历、滑动窗口最大值（单调队列）、前 K 个高频元素（优先级队列）。
经典题目
232.用栈实现队列、225.用队列实现栈、20.有效括号、150.逆波兰表达式、239.滑动窗口最大值
🌳 二叉树 ★重点
理论基础
满二叉树、完全二叉树、二叉搜索树（BST）、平衡二叉搜索树（AVL）。遍历方式：深度优先（前中后序）和广度优先（层序）。
递归三部曲
① 确定参数和返回值 ② 确定终止条件 ③ 确定单层递归逻辑。此法贯穿所有二叉树递归题目。
属性类
对称二叉树、最大/最小深度、平衡二叉树、所有路径、左叶子之和、完全二叉树节点个数。
修改与构造
翻转二叉树、中+后序构造二叉树、最大二叉树、合并二叉树。
二叉搜索树
BST 中序遍历为递增序列。验证 BST、最近公共祖先、插入、删除（5种情况）。
经典题目
144/94/145.遍历、102.层序、226.翻转、101.对称、104.最大深度、700.BST搜索、701.BST插入
🔄 回溯算法 ★重点
理论基础
回溯 = 穷举搜索，适用于组合/切割/子集/排列/棋盘问题。可抽象为 N 叉树：宽度 = for 循环，深度 = 递归。
回溯三部曲
① 确定回溯函数参数 ② 确定终止条件（收集结果）③ 确定遍历搜索过程（for循环+递归）。
树层去重 vs 树枝去重
Carl 自创的两个概念。树层去重：同一层避免重复选择（used 数组）；树枝去重：一条路径上避免重复使用。这俩词一出，回溯去重就通了。
经典题目
77.组合、216.组合总和III、17.电话号码字母组合、39/40.组合总和、46.全排列、51.N皇后、37.解数独
⚡ 贪心算法
理论基础
每阶段选局部最优，达到全局最优。关键：证明局部最优可推出全局最优。无固定套路，先举反例，找不出就试试贪心。
经典题目
455.分发饼干、376.摆动序列、53.最大子序和、122.买卖股票II、55.跳跃游戏、45.跳跃游戏II、435.无重叠区间
🧩 动态规划 ★重点
理论基础
面试最难也是最高频的算法。只讲几道题远远不够，堆砌题目只会"一看就会，一写就废"。
动规五部曲
① 确定 dp 数组含义 ② 递推公式 ③ dp 初始化 ④ 遍历顺序 ⑤ 举例推导 dp 数组。
背包问题
0-1背包（倒序遍历）、完全背包（正序）。先遍历物品再背包=组合数，反过来=排列数——这是关键区别。
股票问题
最多买卖1次/2次/多次/含冷冻期/含手续费——均基于同一套状态机框架：每天有持有/不持有两种状态。
子序列问题
最长递增子序列、最长公共子序列、编辑距离（两个字符串DP的经典代表）、回文子串、最长回文子序列。
经典题目
509.斐波那契、70.爬楼梯、62.不同路径、416.分割等和子集、518.零钱兑换II、300.最长递增子序列、1143.最长公共子序列、72.编辑距离
🎯 核心方法论
| 专题 | 方法论 | 步骤 |
|---|---|---|
| 二叉树 | 递归三部曲 | 参数/返回值 → 终止条件 → 单层逻辑 |
| 回溯 | 回溯三部曲 | 函数参数 → 终止/收集 → for循环+递归 |
| 动态规划 | 动规五部曲 | dp含义 → 递推 → 初始化 → 遍历 → 打印 |
算法相关书籍
算法的野心
美 吉尔·勒珀
算法思维训练
斯洛伐克 米哈尔·福里谢克
斯图尔特微积分（第九版·下）
加 詹姆斯·斯图尔特（James Stewart）
计算机算法基础 第2版
深入浅出程序设计竞赛（进阶篇）
汪楚奇 著
代码随想录——跟着Carl学算法
孙秀洋
程序语言的奥妙
杉浦贤
数据挖掘原理与算法
毛国君等编著
柔性字符串匹配
纳瓦罗
数学建模算法与应用习题解答
司守奎
隐私保护数据发布：模型与算法
吴英杰
数据结构与算法
章炯民, 章炯民, 黄国兴, 黄国兴
算法与数据结构
数据结构、算法与应用
齐悦, 夏克俭, 姚琳编
快速傅里叶变换
K. R. Rao
编译原理
Alfred V.Aho, Jeffrey D.Ullman, Ravi Sethi
离散数学及其应用（原书第6版）
美 Kenneth H. Rosen
数据结构
Michael Main
应用组合数学
罗伯茨
计算理论基础
Harry R. Lewis, Christos H. Papadimitriou, 哈瑞·刘易斯