编程面试题库

题型： 双指针·复杂度： 时间 O(n)，空间 O(1)

在有序数组的两端各放一个指针。和太小就右移左指针，和太大就左移右指针。数组有序保证了你永远不会跳过一个有效的数对——面试官想听你大声说出的，正是这个不变量。

题型： 哈希表 / 计数·复杂度： 时间 O(n)；字母表固定时，空间 O(1)

统计第一个字符串里各字符出现的次数，扫描第二个字符串时逐个减掉，最后检查所有计数是否都回到零。在被问到之前就主动提出进阶问题：如果是完整的 Unicode 字符，固定 26 个槽位的数组就不管用了——改用哈希表。

题型： Floyd 快慢指针·复杂度： 时间 O(n)，空间 O(1)

一个指针每次走一步，另一个每次走两步；如果它们相遇，就说明有环。准备好应对经典的追问——找到环的入口：把其中一个指针放回链表头，然后两个指针每次各走一步，直到再次相遇。

题型： 摩尔投票法（Boyer–Moore）·复杂度： 时间 O(n)，空间 O(1)

维护一个候选元素和一个计数器：遇到相同元素就加一，不同就减一，计数器归零时就更换候选。因为多数元素出现的次数超过 n/2，它最后一定能留下来。讲清楚它「为什么」一定能留下来，才是这道题真正要考的。

题型： 一次遍历，维护最低价·复杂度： 时间 O(n)，空间 O(1)

记录到目前为止的最低价格，以及如果今天卖出能获得的最大利润。一次遍历，两个变量。这是「携带最优前缀状态」这一思路最简单的例子，后面在 Kadane 算法中还会再次出现——点出这层联系能加分。

题型： 排序 + 线性扫描·复杂度： 时间 O(n log n)，空间 O(n)

按区间起点排序，然后扫描：如果当前区间的起点在上一个合并区间的终点之后，就直接追加；否则把合并区间的终点延伸到两者中的较大值。真正起作用的是排序——要把这一点说出来，并处理好比较时的边界情况（首尾相接的区间）。

题型： 哈希集合 + 序列起点·复杂度： 时间 O(n)，空间 O(n)

把所有数字放进一个集合；只从前一个数不存在的数字（即序列起点）开始计数，再一路往后数。每个元素最多被访问两次——当有人质疑「这里明明有嵌套循环」时，你就靠这一点来捍卫 O(n) 的结论。

题型： 前缀积 / 后缀积·复杂度： 时间 O(n)，除输出数组外额外空间 O(1)

不用除法，遍历两次：第一次在每个位置填入它左边所有元素的乘积，第二次从右往左扫，再乘上它右边所有元素的乘积。用除法的解法遇到 0 就会出错——面试官通常会明确禁止用除法。

题型： 辅助栈与不变量·复杂度： 每次操作 O(1)，空间 O(n)

在存值的栈旁边再维护一个最小值栈，它的栈顶永远是当前所有元素中的最小值——入栈时压入 min(新值, 当前栈顶)，出栈时两个栈同步弹出。这是一道设计题：评分看的是不变量，而不是代码量。

题型： 哈希表 + 双向链表·复杂度： 每次 get/put 为 O(1)，空间 O(capacity)

用哈希表在 O(1) 时间内定位到双向链表中的节点，链表按最近使用的顺序排列；访问时把节点移到表头，超出容量时从表尾淘汰。哨兵头尾节点能消除所有判空的边界情况——在开始写代码之前就提出来。

题型： 网格 BFS/DFS 洪水填充·复杂度： 时间 O(rows × cols)

扫描整个网格；每遇到一个未访问的陆地格子，就从它开始做一次洪水填充（DFS 或 BFS），把整座岛标记为已访问，统计起点的个数即可。说明你标记已访问的策略（原地「沉岛」还是另用一个集合），以及在超大网格上递归过深的风险——这才是资深的信号。

题型： 拓扑排序 / 环检测·复杂度： 时间 O(V + E)

把先修关系建模成一张有向图；「能不能修完所有课程」恰好等价于「这张图有没有环」。Kahn 算法（反复移除入度为 0 的节点）或 DFS 三色标记法都可以——选一种，并讲清楚为什么最后有剩余的节点就说明有环。

题型： BFS + 按层记录队列长度·复杂度： 时间 O(n)，空间 O(width)

用队列做 BFS，但在每一轮开始时记下队列的长度，这样就能每层输出一个列表。「记下队列长度」这个技巧是可以复用的核心——锯齿形层序遍历和二叉树的右视图，都是同一个循环，只是收集结果的方式不同。

题型： 上下界传递 / 中序遍历·复杂度： 时间 O(n)，空间 O(height)

递归时带上一个允许的 (min, max) 区间，每往下一层就收紧一次——或者做一次中序遍历，检查结果是否严格递增。经典的陷阱是只拿子节点和父节点比较；赶在面试官之前，自己先把反例构造出来。

题型： 双向哈希映射（双射）·复杂度： 时间 O(n)，空间 O(n)

既要把模式中的字符映射到单词，「也」要把单词映射回字符——只做单向映射的话，模式「ab」也会匹配「dog dog」。双向检查这个双射就是全部的诀窍；要说出「双射」这个词，并在写代码之前处理好长度不一致的情况。

题型： 隐式序列上的环检测·复杂度： 每步 O(log n)；用 Floyd 算法时空间 O(1)

不断把一个数替换成它各位数字的平方和，结果要么到达 1，要么进入循环——所以这其实是换了个马甲的「环形链表」。可以用一个记录已出现数字的集合来检测循环，也可以用 Floyd 快慢指针做到 O(1) 空间，让面试官眼前一亮。点出它可以归约为环检测问题，才是资深的做法。

题型： 需要证明的贪心·复杂度： 时间 O(n)，空间 O(1)

如果汽油总量 ≥ 总消耗，就一定有解，而且解是唯一的。扫描一遍，同时记录油箱里的累计油量；一旦变成负数，失败的这一段里任何一个加油站都不可能是起点——从下一个加油站重新开始。这道题考的是如何论证这次「跳过」是对的，而不是循环本身。

题型： 贪心 / 隐式 BFS 分层·复杂度： 时间 O(n)，空间 O(1)

把 k 步之内能到达的下标看作 BFS 的一层：记录当前这一层的右边界，以及目前能到达的最远位置；走过边界时，跳跃次数加一，并把边界延伸到那个最远位置。把它看成「不用队列的 BFS」，就能解释清楚这里的贪心「为什么」是最优的。

题型： 三段式线性合并·复杂度： 时间 O(n)，空间 O(n)

先输出所有在新区间开始之前就结束的区间，再把所有与之重叠的区间并入新区间（取最小起点、最大终点），最后输出剩下的区间。输入本身有序，所以只需遍历一次，不用重新排序——如果被问到为什么这题更简单，就拿它和「合并区间」做个对比。

题型： 原地矩阵变换·复杂度： 时间 O(n²)，空间 O(1)

顺时针旋转 90° = 先转置，再把每一行反转。两次干净的遍历、O(1) 额外空间，比在压力下手推四个位置的循环交换要好——但如果面试官不满足于这个技巧、继续追问，你要能解释清楚坐标映射 (i,j) → (j, n−1−i)。

题型： 借用存储空间原地标记·复杂度： 时间 O(m×n)，空间 O(1)

用第一行和第一列来存放哪些行、哪些列需要置零的标记，再用两个布尔变量记住第一行和第一列自身的状态。把空间优化的阶梯大声讲出来——O(mn) 的复制 → O(m+n) 的集合 → O(1) 的借用存储——因为考的正是这个阶梯本身。

题型： 排序 / 计数桶·复杂度： 排序法 O(n log n)，计数桶 O(n)

降序排序后，找出满足 citations[i] ≥ i+1 的最大 i——或者不排序，用上限为 n 的计数桶做到 O(n)。写代码之前先把定义说准确；这道题上大多数失误都是误读了「有 h 篇论文的被引次数至少为 h」，而不是算法本身出错。

题型： 拓扑排序并输出顺序·复杂度： 时间 O(V + E)

和「课程表」是同一张图，但这次 Kahn 算法真正派上了用场：入度为 0 的节点出队的顺序，「就是」一个合法的选课顺序。如果输出的顺序比课程总数短，就说明有环——返回空数组。再提一下另一种解法：把 DFS 的后序遍历结果反转。

题型： 滑动窗口 + 满足条件计数器·复杂度： 时间 O(n)，空间 O(alphabet)

先扩展右边界，直到窗口覆盖所有需要的字符（用一个「已满足 / 需满足」的计数器来跟踪，而不是每一步都比较整张哈希表），再在保持有效的前提下把左边界收缩到最小，并记录最优结果。正是这个计数器优化让算法保持 O(n)——要明确解释出来。

题型： 双指针 + 维护左右最大值·复杂度： 时间 O(n)，空间 O(1)

每根柱子上方的水量 = min(左侧最大值, 右侧最大值) − 柱子高度。两个指针从两端向中间移动，每次处理当前最大值较低的那一侧，因为那一侧的边界已经确定了。讲清楚为什么可以如此确定——这就是整道题的核心。