《面试常考算法题(二)》已经来了。上一期聊了几个基础方向，评论区不少人说“思路能懂，但一到面试现场就卡住”。我特别理解这种感觉，所以这一期我换了个讲法：不只给你题目和解法，更让你看到拿到一道题之后，大脑应该怎么一步步运转。今天挑的这四道题，基本是近三年中小厂到中大厂笔试面试里出现频率最高的几个类型，每一道都能讲出很多门道。
先说明一下，这系列文章默认你用 Python 写算法。不是 Python 就一定比 Java、C++ 好，而是 Python 的表达足够接近伪代码，可以让你把注意力放在思路推导上，而不是陷入指针、内存这些实现细节里。尤其对于面试场景，你要让面试官一眼看懂你在做什么，Python 天然的简洁优势非常明显。
1. 先聊聊算法面试到底在考什么
面试官让你写算法题，真的只是想看你会不会背题吗？当然不是。我面过不少人，也被人面过，慢慢摸清了这道环节的真实意图：一考逻辑思维的清晰度，二考代码落地能力，三考沟通和应变能力。
很多同学有一个误区，觉得只要刷题数量上去了，面试就没问题。于是照着题单从第一题刷到第五百题，一道题看五分钟没思路就直接翻题解。这种刷法的效率低到什么程度呢？低到你刷完一百道之后，遇到一道从没见过的变形题，依然毫无头绪。
真正有效的准备方式是抓“解题套路”。算法题看起来千变万化，但剥开外壳，内核就那么几十种：枚举、递归、分治、二分、双指针、滑动窗口、回溯、动态规划、贪心、图论、并查集、字典树、堆、单调栈……你把每一个套路的适用场景和思维路径吃透，再遇到新题的时候，本质上是“往已知模型上套”的过程。
1.1 面试官真正想看的能力模型
在真实面试流程里，算法题通常不是孤立的。面试官会先让你说思路，再让你动手写，最后让你跑几个测试用例。如果你只闷头写代码，不解释，面试官其实很难判断你是真的懂了还是背的。
我自己的体会是，算法面试要呈现的是以下三条线：
第一条线是思路推导。你要能说清楚“为什么想到用这种算法”“暴力解是什么样”“哪些条件让我决定做优化”。哪怕最后没写出来，思路清晰的人往往也比闷头写对的人分数高。
第二条线是代码实现。写到什么程度算好？第一不能有明显语法错误，第二边界条件要处理干净，第三代码风格要整洁。全篇给变量起名成 a、b、c 的这种，就算AC了面试官也会皱眉头。
第三条线是验证能力。写完代码之后，主动举测试例子跑一遍自己的逻辑，尤其是空输入、单元素、全相同元素这些边界场景。这种习惯非常加分。
1.2 为什么建议用 Python 刷题
有些人总觉得 C++ 刷题显得“更硬核”，但我的观点是：面试的时间就这么点，你的精力应该花在呈现解题思路上，而不是花在手动管理内存和迭代器上。Python 的语言特性天然适合算法表达，主要有这几点优势。
第一点，Python 的列表、字典、集合等内置结构非常接近算法抽象层。比如“判断元素是否出现过”，你不需要像 C++ 那样纠结于 unordered_set 还是 set，直接 set 搞定，时间复杂度的讨论也清晰得多。
第二点，Python 支持多重赋值、切片、列表推导式，很多代码可以写得很短且可读性高。比如交换两个变量就一行a, b = b, a，这在写排序算法的时候尤其舒服。
第三点是，当你讲思路的时候，Python 代码几乎可以直接贴在思路后面，中间没有“翻译”的损耗。面试官看着你写的代码，再听你的讲解，他听到的是算法逻辑本身，而不是“C++ 里这个 vector 怎么初始化”之类的实现噪音。
不过有一点要提醒：用 Python 不代表可以不关心复杂度。Python 本身就是一门较慢的语言，你的算法如果复杂度不理想，面试官很容易看出来，所以复杂度分析反而是重点加分项。
2. 高频题一：滑动窗口套路，拿下“无重复字符的最长子串”
这道题是 LeetCode 第 3 题，属于经典中的经典。如果说有哪道题值得你背到肌肉记忆，那这道题一定排前三。真题版本有个变形是“找最长不含重复字符的子串的长度”，本质上完全一样。
题目给你一个字符串，比如s = "abcabcbb"，要你找出其中不含有重复字符的最长子串的长度。所谓子串，就是连续的一段字符。"abc"是子串，"acb"不是，因为不连续。
2.1 从暴力解开始找感觉
拿到这道题，不要一上来就想着写最优解，先想暴力解。暴力解的方式是：枚举每个左端点 i，然后从 i 开始向右扩，把字符逐个加入集合，直到遇到重复字符停止，记录当前最长长度。
def length_of_longest_substring(s: str) -> int: n = len(s) ans = 0 for i in range(n): seen = set() for j in range(i, n): if s[j] in seen: break seen.add(s[j]) ans = max(ans, j - i + 1) return ans这个暴力解的时间复杂度是 O(n²)，在字符串长度稍长时就会超时。但它告诉了我们一个关键信息：这个问题的本质是“维护一个无重复字符的滑动窗口”，而且窗口是向右单调移动的。
2.2 滑动窗口的思维转变
暴力解效率低的根本原因在于：每次左端点 i 移动时，我们都重新从 i 开始扩展右端点，之前已经扫描过的字符信息被丢掉了。
聪明一点的做法是：左指针和右指针都只向右移动，不回头。右指针负责探索新字符，左指针负责在发现重复时收缩窗口。整个过程就像一条贪吃蛇，头往前探索，尾在后面跟进。
具体思路是这样的。我们维护一个 set，用来记录当前窗口内有哪些字符。右指针逐步向右移动，每遇到一个新字符就检查它是否在 set 里：
- 如果不在，说明可以扩展窗口，把这个字符加入 set，更新答案。
- 如果在，说明当前窗口已经不能继续扩展了，需要移动左指针，把左指针指向的字符从 set 中移除，直到把那个重复的字符移出窗口为止。
代码实现看起来是这个样子：
def length_of_longest_substring(s: str) -> int: n = len(s) left = 0 seen = set() ans = 0 for right in range(n): while s[right] in seen: seen.remove(s[left]) left += 1 seen.add(s[right]) ans = max(ans, right - left + 1) return ans这里最精髓的地方在于while s[right] in seen。重复的元素可能不只有一个，比如窗口里是a, b, c, b，你只删一个左边界不一定能删掉重复的b，所以要循环地删，直到把那个与s[right]相同的字符从集合里挪出去。
2.3 一个容易踩的坑：别用 remove 而忽略重复值
这里要注意一个细节：set.remove()在元素不存在时会抛异常。上面代码里因为有while条件保证元素必然存在，所以安全。但如果你对字符串处理的经验不足，容易在其他题目里写出不安全的 remove 调用。
另外，严格来说这个写法的时间复杂度是 O(n)，因为左右指针都只遍历了字符串一次，内层 while 循环总共执行的次数也以 n 为上限。空间复杂度 O(min(m, n))，m 是字符集大小。
2.4 滑动窗口的通用套路总结
这道题只是滑动窗口的入门题。只要你吃透了它的“维护窗口内性质 + 右扩左缩”的框架，后面很多题都能直接套：最小覆盖子串、字符串排列、替换后的最长重复字符……核心动作都是一样的，区别只在于窗口内维护的信息是什么、何时收缩窗口。
面试官接下来极大概率会让你变形：比如让你返回最长子串的起始位置，或者要求不借助 set 而用字典记录字符最后出现的位置。你都可以在原解法上改。用字典的版本可以做到左指针直接跳到重复字符的下一位，这是进阶优化，但对理解要求更高。先用 set 把框架吃透，能把这道题的每一步讲清楚，比背一个更“高级”但讲不明白的写法要好得多。
3. 动态规划入门到熟练：三分钟理清“打家劫舍”
动态规划是算法面试里最容易让人恐惧的模块。但说实话，面试常考的动态规划题没有你想象的那么难，大部分都集中在几种典型模型上：一维 DP、二维 DP、背包问题变种、区间 DP。今天选的“打家劫舍”就是最典型的一维 DP 题，LeetCode 第 198 题。
题目本身是个小故事转换来的：你是一个猎人，要偷一排房屋里的财物，每间房屋有不同数量的宝物，但是不能偷相邻的两间屋子，否则会触发警报。请问一次最多能偷多少。
3.1 怎么判断这道题要用动态规划
拿到任何一道题，第一步都是判断题型。看到“不能相邻”“最大价值”这类词，你就要有“这可能是动态规划”的直觉。判断标准也很简单：问题的决策会影响之后的决策，且子问题之间有重叠。
具体到打家劫舍：你在决定要不要偷第 i 间房屋时，需要考虑前面偷到了哪间。如果偷了第 i-1 间，那第 i 间就不能偷；如果没偷第 i-1 间，就可以偷。这是一个有后效性的决策问题，天然符合 DP 的特征。
3.2 状态定义和转移方程推导
动态规划的难点在于定义状态。这里可以定义dp[i]表示“偷窃到第 i 间房屋时，能够获得的最大金额”。那么对第 i 间房屋，你有且仅有两个选择：
- 选择偷它：那么第 i-1 间不能偷，收益是
dp[i-2] + nums[i]。 - 选择不偷它：那么收益就是前 i-1 间的最大值，即
dp[i-1]。
两者取最大，就得到状态转移方程：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])基础条件就两个：只有一间房时，答案就是nums[0]；有两间房时，答案是max(nums[0], nums[1])。
def rob(nums: list[int]) -> int: n = len(nums) if n == 0: return 0 if n == 1: return nums[0] dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) return dp[-1]3.3 空间优化：从 O(n) 到 O(1) 的思维跨越
很多人在这一步就停了，觉得能 AC 就行。但如果你真的在面试，面试官一定会追问一句“还能优化吗”。动态规划数组不是必须的，因为dp[i]只依赖dp[i-1]和dp[i-2]，也就是说你只需要保存前两个状态，不需要保留整个数组。
def rob(nums: list[int]) -> int: prev2 = 0 prev1 = 0 for num in nums: cur = max(prev1, prev2 + num) prev2, prev1 = prev1, cur return prev1这段代码一开始看可能有点绕。实际上prev1表示“截止到上一间的最大收益”，prev2表示“截止到上上间的最大收益”。每遍历一个新值，就计算当前最大收益，然后更新这两个变量。这样空间复杂度从 O(n) 降低到 O(1)。
3.4 面试追问的多种变形
这个题目在面试里出现的概率极高，而且面试官通常不会只让你写基础版。最常见的变形是“房屋围成一圈”，也就是首尾不能同时偷。解法也很清晰：把环形拆成两个线性问题，一个不含第一间房，一个不含最后一间房，分别用打家劫舍的解法，取最大值。
def rob_cycle(nums: list[int]) -> int: if len(nums) == 1: return nums[0] return max(rob(nums[:-1]), rob(nums[1:]))就这么几行。把一个大问题拆成两个已经解决过的子问题，这种思维其实比背代码重要得多。面试官就是想看到你有这种“把陌生问题转化成熟悉问题”的能力。
4. 一题吃透回溯算法：全排列里藏着递归的精髓
回溯算法是面试里的另一座大山，而“全排列”是回溯算法最经典、最基础的代表题目。LeetCode 第 46 题，题目简洁：给你一个不含重复数字的数组 nums，返回它的所有全排列。
比如nums = [1, 2, 3]，输出是[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]。
4.1 回溯的直觉从哪里来
请你想象一下：你要手工列出[1, 2, 3]的全排列，你会怎么做？大概率是先固定第一个位置是 1，然后对剩下的[2, 3]做全排列；再把第一个位置换成 2，对剩下的[1, 3]做全排列。这个“固定一个，递归处理剩下的”过程，就是回溯算法的骨架。
回溯的本质就是深度优先搜索（DFS）在解空间树上的遍历。每走一步就做出一个选择，如果发现此路不通或者已经走完，就回退到上一步撤销选择，再尝试其他分支。
4.2 回溯题的标准模板
回溯题有一个万能的模板，大体上是这样的：
def backtrack(路径, 选择列表): if 满足结束条件: 将路径加入结果集 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择套到全排列上，代码写出来是这样：
def permute(nums: list[int]) -> list[list[int]]: res = [] used = [False] * len(nums) path = [] def backtrack(): if len(path) == len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) backtrack() used[i] = False path.pop() backtrack() return res这里有几个值得反复咀嚼的点：首先是res.append(path[:])，为什么这里必须用path[:]，而不是直接res.append(path)？因为path是一个列表对象，你后续不断地 append 和 pop 修改的是同一个对象。如果直接把path放进去，最后结果集里存的其实都是同一个列表的引用，等回溯结束，所有的元素都会变成同一个状态，导致结果全是空列表。这个问题我见过无数新手踩坑。
4.3 剪枝是什么，什么时候需要剪枝
回溯算法最让人头痛的问题是复杂度。全排列的复杂度是 O(n * n!)，因为排列总数为 n!，每个结果需要复制 n 个元素。在 LeetCode 上题目规模通常不大，所以直接回溯没问题。
但如果你遇到的题目是，数组里有重复数字，要求返回不重复的全排列，那你就得在回溯的过程中加一个“剪枝”操作。剪枝的意思是提前终止一些注定会重复的分支。
以 LeetCode 第 47 题（全排列 II）为例，核心就是先排序，然后在 for 循环里判断：如果当前元素和上一个元素相同，且上一个元素还没被使用过，就跳过当前的枚举。
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue这一步逻辑初看可能费解。你要明白它背后的原理：同一层递归中，如果前一个相同的数字没有被用过，说明这个相同的值已经在前面被当作分支尝试过了，当前分支会产生和之前一模一样的结果，所以直接跳过。
剪枝是回溯题里的核心优化手段，也是区分“会套模板”和“真懂了回溯”的关键分水岭。面试官很喜欢在基础回溯题后面追加“如果有重复元素怎么办”这个问题，本质上就是在考察你对剪枝的理解。
4.4 回溯与状态重置
最后再强调一下“撤销选择”为什么重要。在回溯里，used[i] = False和path.pop()这两行代码缺一不可。它们的意义是把状态恢复到进入该分支之前，让其他分支在相同的起点上继续探索。
我见过不少面试者逻辑上清楚要做什么，但写代码时少写了状态恢复，结果递归返回后used数组全变成了True，后面的分支全部被跳过了。只要你记住“回溯 = 递归 + 状态恢复”这个公式，这类问题就绝对不会犯低级错误。
5. 面试里的“算法思维”养成法：别急着刷题，先学会拆题
很多读者问过我，说热词里现在都在讲“python算法思维题”，到底什么才叫算法思维？跟普通刷题有什么区别？
我的理解是，思维题更强调你面对一个从未见过的问题时，如何把它分解成已知模型，而不是凭记忆背答案。面试中大多数算法题不是你刷过的原题，而是原题的变体。你要练的就是“看出原题”的能力。
5.1 拿到一道新题的思维路径模板
我在准备面试的时候，给自己总结了一套解题步骤，遇到任何算法题都按这个顺序走：
第一步，画例子。不管题目描述得多抽象，先自己造一个具体的输入，把答案手工推演出来。这个过程会逼你理解题目到底在问什么，而不是急着写代码。
第二步，想暴力解。别觉得暴力解丢人，暴力解最大的价值是帮你找到问题的“朴素逻辑”。面试时先把暴力解说清楚，再提出优化方向，这个思考路径本身就有分。
第三步，判断题型。这一步的关键词匹配法很管用。看到“最值”想 DP 和贪心；看到“连续子数组”想前缀和、滑动窗口；看到“所有组合/排列”想回溯；看到“第 K 大”想堆或快速选择；看到“有序数组搜索”想二分。这个匹配表不绝对，但对大多数面试题都适用。
第四步，估算复杂度。在开始写代码之前，心里先算一下暴力解的复杂度和优化后所能达到的目标复杂度。这两个数字能帮你判断优化方向是否合理。
第五步，写代码、跑样例。写完后不要立刻说“好了”，主动用手里的简单例子跑一遍逻辑，再想一想边界条件。
5.2 如何用最短的时间刷出最大的效果
关于刷题数量和频率，我的观点是：与其一天刷十道新题，不如一天吃透两道题，并且一周后回来重写一遍。记忆是会衰减的，重写一次远比新做一道题更能巩固套路。
关于“看题解”这件事也要有原则。我自己的原则是：一道题如果想了三十分钟还没有任何成型的思路，那就直接看题解，但看完题解后必须合上答案，自己再独立写一遍。如果第二天能默写出来，这道题才算真正属于你了。
再推荐一个练习方法：找一个面试搭子，互相给对方讲题。别小看这个办法，讲题是最能暴露知识漏洞的方式。你可能觉得自己懂了，但真解释的时候才发现很多细节根本说不清楚，那你在面试现场也会一样卡住。
5.3 计算复杂度时 Python 特有的坑
还有一个很重要但很多人忽略的点：在 Python 里算复杂度，要考虑内置操作的时间代价。比如判断一个元素是否在列表里，复杂度是 O(n)；但判断是否在 set 或 dict 里，复杂度是 O(1)。又比如list.pop(0)是 O(n) 的操作，因为它要搬移所有元素；而list.pop()是 O(1) 的。用collections.deque才能保证两端操作都是 O(1)。
这些细节直接决定你的解法到底能不能过测试。我见过不少同学把列表当队列用，结果在数据量大时超时，还一脸困惑。这些基础的复杂度知识，是 Python 刷算法题必须跨过的一层门槛。
6. 常见问题与实战排查技巧
平时在我的交流群里，总有同学在面试后跑来复盘，说“我明明刷了不少题，怎么现场还是写不出来”。我帮大家总结出了几个高频问题，也附上了对应的排查方向。
第一个问题是思路停留在大脑里，没落笔。有些人习惯在脑内跑代码，觉得逻辑清晰了就直接写。但代码实际写出来往往会发现 index 不对、边界没处理、循环条件写反。解决建议是：一定要养成在纸上画例子的习惯，哪怕只是简单地写几个箭头和标记，都比干想靠谱。
第二个问题是边界条件考虑不全。空数组、只有一个元素、所有元素相同、元素已经有序，这些是算法题最常见的边界情况。每次写完代码，先主动跑这几个用例，不要等面试官问。
第三个问题是时间压力下心态崩了。这无法靠刷题解决，只能靠多模拟面试来解决。自己给自己定 20 分钟倒计时，用面试白板方式练习。我个人的经验是，一旦你能在模拟面试中平静地讲出思路、写出实现、跑通测试，真实面试时的紧张感会大幅降低。
第四个问题是基础 API 不熟。Python 的排序sorted、堆heapq、双端队列deque、计数器Counter、默认字典defaultdict，这些是刷题高频工具。不熟悉它们的话，面试时连基础功能都要现场查文档，效率极低。建议把每个常用集合类的方法过一遍，能做到不看文档直接写。这里有一个很讨巧的小技巧：你可以在面试前把collections、heapq、bisect等常用模块的常用方法默写一遍，确认自己对它们足够熟悉，这样面试时就不会因为 API 卡壳。
第五个问题是只写代码不讲思路。很多性格内向的同学容易犯这个毛病。面试官其实非常想听到你内心的思考过程，即使想法不完整也没关系，可以先说“我想先试试枚举”，再说“但这样复杂度是 O(n²)，我希望能优化到 O(n log n)”，面试官会顺着你的思路给提示。反过来，如果你一直沉默，面试官想帮你都找不到入口。
7. 做题之后的复盘方法：让每一道题都变成一类题
最后分享一个我一直在用的复盘方法：每做完一道题，不要急着做下一道，花几分钟在题目旁边记三行笔记。第一行写这题属于哪个题型，第二行写最优解的核心思路是什么，第三行写自己踩了哪个坑或者哪个地方想了很久才想通。这样一个星期后打开题目列表，你看到的就不是一个接一个的标题，而是一张你自己的知识图谱。
用打家劫舍举个例子，你可以记下：题型是线性 DP，核心是“选或不选”的状态决策，我踩的坑是忘记单独处理 n=0 和 n=1 的情况。用全排列举例：题型是回溯，核心是递归+状态恢复，我踩的坑是忘记path[:]复制导致结果全空。这些笔记会在你面试之前提供非常高效的复习路径。
我自己刷题的习惯是每晚固定花半小时，周一三五做新题，二四日重做旧题，周末把这一周的笔记通读一遍。坚持三个月，效果远好于那种“周末一坐一下午刷五十道”的集中式冲刺。算法思维的养成本身就靠日拱一卒，不要指望临时抱佛脚能解决问题。
这一期选的四道题，滑动窗口、一维 DP、回溯、思维模型，如果你能真正吃透，基本可以覆盖面试中将近三分之一的常见题型。下一期我打算重点讲讲二叉树的递归套路和链表题的指针操作，这两个方向在面试里的出场率也相当高。如果你有自己特别怕的题型，也可以评论区告诉我，我来安排。
