算法题在技术面试里的地位说实话已经到了不用强调的程度。不管你是面开发岗还是算法岗几乎每一轮技术面都会有一道白板题或者在线编程题等着你。我见过太多候选人项目经历聊得头头是道一到手撕代码环节就卡壳要么思路卡住不动要么代码写出来了但边界条件一堆问题。这篇内容就是想把面试里最高频的几类算法题拎出来从核心思路、Python实现到避坑细节一次性讲透。适合正在准备技术面试、刷题遇到瓶颈、以及想系统梳理高频题型的同学。这次先聚焦几个最容易被考到的基础题型数组双指针、哈希表、滑动窗口、链表操作、二叉树遍历、动态规划入门。这些题目一上来不是让你背题而是通过它们考察你对数据结构、时间复杂度和边界条件的敏感度。文章里每个部分都有可以直接抄走的模板代码也有我自己刷题和面试别人时总结出来的经验教训耐心看完动手练上几遍面试遇到同类型题目不会慌。1. 面试算法题到底在考什么先建立答题框架1.1 高频考点面试官真正想看到的很多刷题新手有个误区以为面试考算法就是比谁刷得多、谁背得熟。其实面试官真正看的不是你的题量而是四件事代码能不能一次写对、边界条件有没有敏感性、解题思路能不能清楚讲出来、复杂度分析是不是到位。这四点里任何一点出问题都可能让整轮面试翻车。我统计过自己参与过的面试场次算法题出题频率大致是这样的数组和哈希表最高大概占三成双指针和滑动窗口占两成链表和二叉树加起来两成左右动态规划和贪心出现频率也不低尤其在中高难度的轮次。所以这篇文章先解决最基础的六类适合作为面试复习的第一站。还有一个很现实的观察很多候选人题目是做过的但面试时不会“讲解”。面试官要听的是你脑子里的推理过程不是只看你闷头敲出来的结果。如果你直接给最优解不再说一句怎么想到的面试官反而会担心你是不是背题。正确的做法是先提暴力解再讲怎么优化到当前方案这样整个思考过程是立体的、可信的。1.2 拿到一道算法题四步走我给身边朋友推荐的面试答题流程固定四个步骤读题、确认边界、说思路、写代码。这个流程看起来简单真正执行到位的人不多。第一步把题目复述一遍用自己的话说给面试官听。这能确认你理解无误也让面试官有机会纠正你的理解偏差。第二步主动问边界条件数组是否有序、是否包含重复元素、输入为空怎么办、能不能用额外空间、数值范围多大。这些问题问出来面试官通常心里给你加分。第三步口头说思路包括时间复杂度和空间复杂度如果可以简单提一下暴力解是什么、为什么不能直接上再引出最终方案。第四步写代码。写完以后不要马上说“做完了”手动跑一遍用例再回头看有没有空指针、索引越界、重复计算这类问题。这套流程练熟了即使题目不完全会做面试官也会觉得你思路清晰、工程素养好。反过来一上来就写代码、写错了还不知所措印象分会大打折扣。1.3 刷题方式如何让练习更有效刷题的具体策略我推荐“分类刷 复盘总结”的组合。不要今天做链表明天做贪心最好是集中两三天只做一类题把这一类题目的常见套路吃透。比如双指针题连刷十道你自然会总结出“有序数组用左右指针、链表题用快慢指针、滑动窗口用左右边界”这样的规律。每一道题做完以后不管做对做错都要自己写一小段复盘考察的数据结构是什么、用了什么经典思路、还有没有别的解法、复杂度是多少。别小看这一步它能把刷过的题真正变成你的东西。我自己就是靠这个方法从刷一道忘一道到后来能够举一反三。2. 数组与双指针从两数之和到三数之和2.1 两数之和哈希表的经典应用两数之和可以说是面试出现频率最高的一道题没有之一。题目本身很简单给定一个整数数组和一个目标值找出数组中和为目标值的两个数返回它们的下标。很多人第一次见到它都能想出暴力解法两层循环枚举所有组合时间复杂度O(n^2)但面试官基本不会满意。优化的关键是用空间换时间。我们遍历数组一遍同时维护一个哈希表键存已经遍历过的数值值存它对应的下标。每遇到一个数就查一下“目标值减当前值”这个差值是否已经在哈希表里如果在说明之前遇到过能和它配对的数直接返回两个下标。def two_sum(nums, target): hash_map {} for i, num in enumerate(nums): diff target - num if diff in hash_map: return [hash_map[diff], i] hash_map[num] i return []有一点必须特别注意顺序是先查哈希表再把当前数放进去。反过来操作在涉及相同元素时会出现问题。举个例子目标值是6数组第一个数是3如果先把3放进去再查差值会发现差值和当前数相等返回的是同一个下标。这种细节就是面试时的加分项主动说出来面试官会知道你真的理解了。2.2 三数之和排序加双指针加去重三数之和是两数之和的进阶版问的是找出数组中所有三个数之和等于0的组合要求不重复。这道题如果用哈希表硬套去重会麻烦到怀疑人生。正确思路是排序加双指针。def three_sum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif total 0: left 1 else: right - 1 return res去重是整个算法最核心的难点分成两处。第一处是固定元素去重当前数如果和上一个数相同直接跳过避免以同一个数作为首位产生重复组合。注意判断条件里的i 0i等于0时没有前一个元素不能比较。第二处是双指针去重找到一组符合条件的三元组后left向右移动到最后一个相同的数right向左移动到最后一个相同的数然后各自再移动一步。我把这一步称为“先跳重再移动”顺序反了会导致漏解或者死循环。复杂度方面排序O(nlogn)固定一个数加上双指针扫描O(n^2)总体O(n^2)。在面试里这道题要能画图演示双指针是怎么收缩的这非常加分。2.3 双指针的使用场景总结双指针真正的使用前提有两个数组有序或者可以利用指针相对位置替代枚举。它是用来消除暴力解法内层循环的不是所有数组题都适合。常见的双指针变体包括对撞指针用于有序数组、回文判断快慢指针用于链表环检测、找中点同向指针用于原地去重、移除元素。面试时说出自己用的属于哪一种能让整个讲解更清晰。3. 滑动窗口处理子串问题的核心套路3.1 什么时候用滑动窗口连续子数组或子串类问题只要目标是求最大最小长度、或者满足某个条件的最短/最长区间大概率可以用滑动窗口。这类题的暴力解法通常是枚举所有子串再判断是否满足条件复杂度至少O(n^2)。滑动窗口的思路是维护一个左闭右开的区间用left和right两个指针控制窗口边界像一条毛毛虫一样在数组上爬过去复杂度降到O(n)。生活化理解一下窗口就像你在一排货架前找一段连续的分区右手不断往右扩展拿到更多商品左手在太多的时候把多余的部分丢掉右手每动一步都看看当前手里的货是否满足条件记录下最优答案。整个过程只需扫一遍货架。3.2 无重复字符的最长子串这是滑动窗口里面最经典的一道题。给定一个字符串找出其中不含重复字符的最长子串长度。思路是right指针向右扩展每遇到一个新字符就先检查窗口内是否已经有它如果有就不断把left往右移直到窗口内没有重复字符每次更新最大长度。def length_of_longest_substring(s): left 0 max_len 0 window set() for right in range(len(s)): while s[right] in window: window.remove(s[left]) left 1 window.add(s[right]) max_len max(max_len, right - left 1) return max_len这里为什么要用while而不是只用一次if去重很多新手会踩坑。因为窗口里可能不止一个重复字符比如窗口内是“abc”新来一个“c”如果只移除一个left字符窗口变成“bc”里面还是有“c”仍然不满足条件。必须用while循环持续移除直到把所有的重复情况都清理掉。这个细节我面试时会专门追问答上来的候选人往往思维严谨度高。3.3 滑动窗口通用模板滑动窗口的代码套路其实很固定背熟模板之后变形题基本都能套。核心结构就是四步right进入窗口、更新窗口状态、while窗口不满足条件时收缩、窗口满足条件后更新答案。left 0 for right in range(len(s)): # 1. 将 s[right] 加入窗口并更新状态 # 2. 更新窗口相关统计信息 while 窗口不满足条件: # 3. 将 s[left] 移出窗口 left 1 # 4. 窗口满足条件更新答案比如“最小覆盖子串”这道hard题也能用这个模板。只是需要额外维护一个字符计数字典和计数器判断什么时候窗口已经包含了目标串全部字符。很多所谓的难题本质上就是模板加一两个辅助数据结构理解了这一点看着难的题也会变成送分题。4. 链表操作反转链表背后的指针学问4.1 迭代反转三指针法反转链表是链表题型里最基础的敲门砖考验的是对指针引用的理解。题目很直接反转一个单链表。如果对链表熟悉的人几分钟就能写完但里面有一个非常容易踩的坑就是指针顺序。先看代码def reverse_list(head): prev None cur head while cur: next_node cur.next cur.next prev prev cur cur next_node return prev第一步保存next_node是整个操作的关键。当cur.next指向被改成prev以后原来的后继节点就丢了不提前保存就无法继续遍历。面试时我常看到有人卡在这一步说明对“改指针前先留后路”这个原则理解不够深。把这个原则说出来比闷头写更让面试官认可。三个指针的行为可以用一句话概括prev是已反转部分的新头cur是当前正在处理的节点next_node是原链表中还未反转的剩余部分。每次循环把cur的next扭转向后然后三个指针整体往后挪一格。4.2 递归反转理解子问题迭代返回的是新的头节点递归同样要做这件事但思路完全不同。递归解法是深度优先先把“当前节点之后的所有节点”反转好再把当前节点接到已反转部分的尾部。def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_headhead.next.next head是递归版本里最精妙的一行。理解它之前先明确一点递归执行完reverse_list_recursive(head.next)后head.next已经成为反转后链表的最后一个节点。此时把head.next的next指针指向head等于把当前节点接到末尾然后断掉head原来向后的指针。递归最深一层返回的节点就是整个链表的最后一个节点它会在每一层递归中保持为new_head返回最终成为反转后的头节点。递归版本的代码很简洁但面试不推荐优先写因为递归深度等于链表长度链表一旦很长会栈溢出而且讲解起来比迭代复杂。可以在面试中先写出迭代版再补充说“递归版也能实现但存在栈深度风险”体现你的知识面而不过度冒险。4.3 链表题的调试经验链表题在本地调试其实是比较麻烦的事打印链表、构造用例都费劲。我的习惯是凡是链表题先画三个节点把prev、cur、next_node三个指针的变化一步步画出来。画图会暴露很多代码里发现不了的问题尤其是循环结束后指针指向哪里、返回的应该是哪个节点这些画一次就理解了。另外一个常见错误是忘记处理空链表和单节点链表。代码里if not head or not head.next这类判断看似简单但很多人一紧张就漏掉。面试写链表题之前先在心里过一遍这两种情况会稳很多。5. 二叉树遍历递归与迭代的面试必背模板5.1 递归模板三行走天下二叉树遍历是算法面试里的常青树前序、中序、后序、层序几乎必考一种。递归版本的三种遍历代码差异极小只是访问节点的位置不同。前序遍历是先访问当前节点再递归左边和右边中序遍历先递归左边访问节点再递归右边后序遍历先递归左右再访问节点。def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right) def postorder(root): if not root: return [] return postorder(root.left) postorder(root.right) [root.val]这种写法简洁好背但实际面试中递归版本价值不大因为很多人都会写体现不出实力。面试官更愿意看到你能写出非递归版本也就是自己维护栈来实现遍历。这也是区分“背模板”和“真理解”的分水岭。5.2 前序与中序的迭代实现前序遍历的迭代实现基于栈逻辑和递归保持完全一致先访问当前节点再处理左子树和右子树。因为栈是后进先出想先处理左子树就得先把右子树压栈这样右子树会最后被处理符合前序“根左右”的顺序。def preorder_iter(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res中序遍历的迭代法就没这么直接了。中序的顺序是“左根右”所以最开始不能直接访问根节点而要先一直往左走把沿途所有节点全部压栈直到走到最左边然后弹出节点访问再去处理它的右子树。def inorder_iter(root): stack [] res [] cur root while stack or cur: while cur: stack.append(cur) cur cur.left node stack.pop() res.append(node.val) cur node.right return res这段代码是二叉树迭代遍历中最容易忘的版本核心在于外层循环条件必须是while stack or cur不能只写while stack。因为刚开始cur不为空、stack为空这是循环能启动的原因后面cur变成右孩子的过程中stk可能空但cur还有值仍然要继续处理。面试时把这一点讲清楚本身就是加分项。5.3 层序遍历的BFS模板层序遍历按层输出用队列实现每一步从队列取出当前层的节点把它们的下一层节点加进去。关键技巧是每轮循环开始前先记录当前队列长度size然后连续处理size个节点。这个size保证了每次循环恰好处理一层不会混层。from collections import deque def level_order(root): if not root: return [] queue deque([root]) res [] while queue: level [] size len(queue) for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res不要图省事直接用for node in queuePython的for循环不会动态反映队列长度变化。必须固定size不然子节点被加进来后本层循环会连带处理下一层节点层级就乱了。这个细节我在代码评审里反复看到属于高发错误。6. 动态规划入门从状态定义到转移方程6.1 什么时候考虑动态规划动态规划是很多人的噩梦也是面试分级的重要分水岭。判断一道题是否应该用动态规划有几个明显的信号求最值、最优策略、最大化最小化问题可以被划分成重叠子问题当前状态可以由前一个或前几个状态推导出来。典型的例子是斐波那契数列、爬楼梯、打家劫舍、背包问题。动态规划的思想核心只有一句话用状态表示阶段用转移方程连接前后阶段用空间记录已经算过的结果避免重复计算。理解了这个本质你就能识别出很多看起来完全不同的题其实是在考同一件事。6.2 爬楼梯的完整推导爬楼梯是动态规划入门题里最友好的一个。题目是这样每次可以爬1阶或2阶台阶问爬到n阶有多少种不同的方法。先考虑最简单的情况爬到第1阶有1种方法爬到第2阶有2种方法。那么第3阶呢你可以从第2阶跨1步上来也可以从第1阶跨2步上来所以总数等于爬到第1阶的方法加上爬到第2阶的方法。以此类推走到第n阶的方法数等于第n-1阶的方法数加第n-2阶的方法数。这个推理过程就是完整的动态规划推导。定义dp[i]为爬到第i阶的方法数转移方程是dp[i] dp[i-1] dp[i-2]初始条件dp[1]1、dp[2]2。代码实现时其实不需要保留整个dp数组因为状态只依赖前两个值滚动两个变量就够def climb_stairs(n): if n 2: return n prev2, prev1 1, 2 for i in range(3, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1空间优化是面试里的加分点。写出O(n)空间的版本后主动说“这个状态只依赖前两个值可以用滚动变量把空间压到O(1)”面试官会立刻对你刮目相看。6.3 打家劫舍的进阶思考打家劫舍的经典描述是一排房子每间房里有不同金额的现金但相邻两间房不能同时偷问能偷到的最大金额。这道题比爬楼梯高一个维度它引入了“选择”概念。定义dp[i]为偷到第i间房时的最大金额对第i间房有两个选择偷或者不偷。偷的话第i-1间不能偷金额是dp[i-2]nums[i]不偷的话金额是dp[i-1]。取两者较大值。def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] dp [0] * len(nums) dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] max(dp[i - 1], dp[i - 2] nums[i]) return dp[-1]这道题最关键的思维转变是状态定义里的dp[i]和一般“前i项和”不太一样它表示的是“到第i间房为止能获得的最大金额”而不是“必然偷第i间房”。很多新手在这个定义上迷糊导致转移方程写错。把“到当前位置的最优结果”这个状态定义想明白很多DP题就通了。6.4 DP题的四步套路DP题无论难度解题套路固定第一定义状态说清楚dp[i]代表什么含义第二写转移方程说明当前状态怎么由前面状态推出来第三初始化边界处理dp[0]、dp[1]这些起点第四确定遍历顺序从小到大还是从大到小一维多维各不同。面试时按这个顺序讲基本不会乱。常见的错误包括初始化只想着dp[0]忘了dp[1]转移方程里索引越界没判断遍历顺序和状态定义冲突。这些坑靠背是背不掉的只有多写几道题、每题复盘一次才能真正建立起DP的直觉。7. 算法题面试的常见问题与避坑实录7.1 面试现场最容易翻车的三个瞬间第一个翻车瞬间是想得太少就开写写完发现思路错了推倒重来还浪费大量时间。正确做法是写代码前先把思路讲完整就算思路有漏洞面试官也可能帮你纠正而不是直接看你翻车。第二个翻车瞬间是写完代码不说测试直接“写完了”。面试官此时会认为你缺乏工程素养代码即使对了也扣分。第三个翻车瞬间是被问到复杂度时答不上来。复杂度分析不是可选项而是必选项每写完一道题都要能清晰解释。一个很实用的办法是写题时在草稿纸上标出算法涉及的数据结构、时间复杂度和空间复杂度写完直接照着说不会临时卡壳。7.2 小规模测试用例面试官最看重的一步写完代码后手动跑一遍小用例是你展示严谨性的最好机会。不要跑太复杂的用例三个元素就够常规用例、边界用例、特殊用例。比如数组题跑一个空数组和单元素数组链表题跑一个空链表和单节点链表二叉树题跑一个只有左子树的树。手动跑的时候不要只在脑子里抽象过直接一行一行指给面试官看边指边说出变量的值变化。这个动作非常有用能暴露索引越界、空指针、死循环等问题。7.3 刷题阶段怎么练刷题阶段的训练方式直接决定面试水平。不要盲目追求刷题数量我见过刷了300道依旧无法通过面试的人也见过只刷了100道但每道都吃透的人顺利拿到offer。区别在于有没有分类总结。建议按照知识点刷先数组再哈希表再链表再到二叉树每个类别刷完以后统一回顾这一类的通用套路。准备一个自己的模板笔记把常见的模板代码整理下来。比如滑动窗口模板、二叉树迭代遍历模板、双指针模板、DP四步法模板。面试前看这些笔记比重新刷题效率高得多。7.4 复杂度的快速估算面试中被问复杂度是常态我建议形成一套固定的分析方法循环嵌套决定时间复杂度的量级递归看递归树的高度和分叉数哈希表操作平均O(1)排序O(nlogn)。空间复杂度主要看额外数据结构用了哈希表就是O(n)用了栈做二叉迭代遍历最坏O(h)h为树高。下面这张表总结了本文提到的题型复杂度方便面试前快速过一遍题型典型解法时间复杂度空间复杂度两数之和哈希表O(n)O(n)三数之和排序双指针O(n^2)O(logn)到O(n)无重复字符最长子串滑动窗口O(n)O(n)反转链表迭代三指针O(n)O(1)二叉树前序/中序栈迭代O(n)O(h)二叉树层序队列BFSO(n)O(n)爬楼梯滚动变量DPO(n)O(1)打家劫舍动态规划O(n)O(1)可优化我自己的经验是复杂度分析不是额外负担而是检验你是否真正理解算法的试金石。如果你说不出复杂度往往说明你对算法的每一步执行还不够清晰。把这篇文章里的每个模板代码都亲手敲一遍再把复杂度讲给自己听效果远比堆刷题量要好。面试真正拼的不是见过多少题而是面对新题时能否快速定位考点、套用模板、排除边界。这些能力没有任何捷径只能在分类练习和复盘总结中慢慢积累。
面试算法高频题型全解析：双指针、滑动窗口、动态规划与Python模板
算法题在技术面试里的地位说实话已经到了不用强调的程度。不管你是面开发岗还是算法岗几乎每一轮技术面都会有一道白板题或者在线编程题等着你。我见过太多候选人项目经历聊得头头是道一到手撕代码环节就卡壳要么思路卡住不动要么代码写出来了但边界条件一堆问题。这篇内容就是想把面试里最高频的几类算法题拎出来从核心思路、Python实现到避坑细节一次性讲透。适合正在准备技术面试、刷题遇到瓶颈、以及想系统梳理高频题型的同学。这次先聚焦几个最容易被考到的基础题型数组双指针、哈希表、滑动窗口、链表操作、二叉树遍历、动态规划入门。这些题目一上来不是让你背题而是通过它们考察你对数据结构、时间复杂度和边界条件的敏感度。文章里每个部分都有可以直接抄走的模板代码也有我自己刷题和面试别人时总结出来的经验教训耐心看完动手练上几遍面试遇到同类型题目不会慌。1. 面试算法题到底在考什么先建立答题框架1.1 高频考点面试官真正想看到的很多刷题新手有个误区以为面试考算法就是比谁刷得多、谁背得熟。其实面试官真正看的不是你的题量而是四件事代码能不能一次写对、边界条件有没有敏感性、解题思路能不能清楚讲出来、复杂度分析是不是到位。这四点里任何一点出问题都可能让整轮面试翻车。我统计过自己参与过的面试场次算法题出题频率大致是这样的数组和哈希表最高大概占三成双指针和滑动窗口占两成链表和二叉树加起来两成左右动态规划和贪心出现频率也不低尤其在中高难度的轮次。所以这篇文章先解决最基础的六类适合作为面试复习的第一站。还有一个很现实的观察很多候选人题目是做过的但面试时不会“讲解”。面试官要听的是你脑子里的推理过程不是只看你闷头敲出来的结果。如果你直接给最优解不再说一句怎么想到的面试官反而会担心你是不是背题。正确的做法是先提暴力解再讲怎么优化到当前方案这样整个思考过程是立体的、可信的。1.2 拿到一道算法题四步走我给身边朋友推荐的面试答题流程固定四个步骤读题、确认边界、说思路、写代码。这个流程看起来简单真正执行到位的人不多。第一步把题目复述一遍用自己的话说给面试官听。这能确认你理解无误也让面试官有机会纠正你的理解偏差。第二步主动问边界条件数组是否有序、是否包含重复元素、输入为空怎么办、能不能用额外空间、数值范围多大。这些问题问出来面试官通常心里给你加分。第三步口头说思路包括时间复杂度和空间复杂度如果可以简单提一下暴力解是什么、为什么不能直接上再引出最终方案。第四步写代码。写完以后不要马上说“做完了”手动跑一遍用例再回头看有没有空指针、索引越界、重复计算这类问题。这套流程练熟了即使题目不完全会做面试官也会觉得你思路清晰、工程素养好。反过来一上来就写代码、写错了还不知所措印象分会大打折扣。1.3 刷题方式如何让练习更有效刷题的具体策略我推荐“分类刷 复盘总结”的组合。不要今天做链表明天做贪心最好是集中两三天只做一类题把这一类题目的常见套路吃透。比如双指针题连刷十道你自然会总结出“有序数组用左右指针、链表题用快慢指针、滑动窗口用左右边界”这样的规律。每一道题做完以后不管做对做错都要自己写一小段复盘考察的数据结构是什么、用了什么经典思路、还有没有别的解法、复杂度是多少。别小看这一步它能把刷过的题真正变成你的东西。我自己就是靠这个方法从刷一道忘一道到后来能够举一反三。2. 数组与双指针从两数之和到三数之和2.1 两数之和哈希表的经典应用两数之和可以说是面试出现频率最高的一道题没有之一。题目本身很简单给定一个整数数组和一个目标值找出数组中和为目标值的两个数返回它们的下标。很多人第一次见到它都能想出暴力解法两层循环枚举所有组合时间复杂度O(n^2)但面试官基本不会满意。优化的关键是用空间换时间。我们遍历数组一遍同时维护一个哈希表键存已经遍历过的数值值存它对应的下标。每遇到一个数就查一下“目标值减当前值”这个差值是否已经在哈希表里如果在说明之前遇到过能和它配对的数直接返回两个下标。def two_sum(nums, target): hash_map {} for i, num in enumerate(nums): diff target - num if diff in hash_map: return [hash_map[diff], i] hash_map[num] i return []有一点必须特别注意顺序是先查哈希表再把当前数放进去。反过来操作在涉及相同元素时会出现问题。举个例子目标值是6数组第一个数是3如果先把3放进去再查差值会发现差值和当前数相等返回的是同一个下标。这种细节就是面试时的加分项主动说出来面试官会知道你真的理解了。2.2 三数之和排序加双指针加去重三数之和是两数之和的进阶版问的是找出数组中所有三个数之和等于0的组合要求不重复。这道题如果用哈希表硬套去重会麻烦到怀疑人生。正确思路是排序加双指针。def three_sum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif total 0: left 1 else: right - 1 return res去重是整个算法最核心的难点分成两处。第一处是固定元素去重当前数如果和上一个数相同直接跳过避免以同一个数作为首位产生重复组合。注意判断条件里的i 0i等于0时没有前一个元素不能比较。第二处是双指针去重找到一组符合条件的三元组后left向右移动到最后一个相同的数right向左移动到最后一个相同的数然后各自再移动一步。我把这一步称为“先跳重再移动”顺序反了会导致漏解或者死循环。复杂度方面排序O(nlogn)固定一个数加上双指针扫描O(n^2)总体O(n^2)。在面试里这道题要能画图演示双指针是怎么收缩的这非常加分。2.3 双指针的使用场景总结双指针真正的使用前提有两个数组有序或者可以利用指针相对位置替代枚举。它是用来消除暴力解法内层循环的不是所有数组题都适合。常见的双指针变体包括对撞指针用于有序数组、回文判断快慢指针用于链表环检测、找中点同向指针用于原地去重、移除元素。面试时说出自己用的属于哪一种能让整个讲解更清晰。3. 滑动窗口处理子串问题的核心套路3.1 什么时候用滑动窗口连续子数组或子串类问题只要目标是求最大最小长度、或者满足某个条件的最短/最长区间大概率可以用滑动窗口。这类题的暴力解法通常是枚举所有子串再判断是否满足条件复杂度至少O(n^2)。滑动窗口的思路是维护一个左闭右开的区间用left和right两个指针控制窗口边界像一条毛毛虫一样在数组上爬过去复杂度降到O(n)。生活化理解一下窗口就像你在一排货架前找一段连续的分区右手不断往右扩展拿到更多商品左手在太多的时候把多余的部分丢掉右手每动一步都看看当前手里的货是否满足条件记录下最优答案。整个过程只需扫一遍货架。3.2 无重复字符的最长子串这是滑动窗口里面最经典的一道题。给定一个字符串找出其中不含重复字符的最长子串长度。思路是right指针向右扩展每遇到一个新字符就先检查窗口内是否已经有它如果有就不断把left往右移直到窗口内没有重复字符每次更新最大长度。def length_of_longest_substring(s): left 0 max_len 0 window set() for right in range(len(s)): while s[right] in window: window.remove(s[left]) left 1 window.add(s[right]) max_len max(max_len, right - left 1) return max_len这里为什么要用while而不是只用一次if去重很多新手会踩坑。因为窗口里可能不止一个重复字符比如窗口内是“abc”新来一个“c”如果只移除一个left字符窗口变成“bc”里面还是有“c”仍然不满足条件。必须用while循环持续移除直到把所有的重复情况都清理掉。这个细节我面试时会专门追问答上来的候选人往往思维严谨度高。3.3 滑动窗口通用模板滑动窗口的代码套路其实很固定背熟模板之后变形题基本都能套。核心结构就是四步right进入窗口、更新窗口状态、while窗口不满足条件时收缩、窗口满足条件后更新答案。left 0 for right in range(len(s)): # 1. 将 s[right] 加入窗口并更新状态 # 2. 更新窗口相关统计信息 while 窗口不满足条件: # 3. 将 s[left] 移出窗口 left 1 # 4. 窗口满足条件更新答案比如“最小覆盖子串”这道hard题也能用这个模板。只是需要额外维护一个字符计数字典和计数器判断什么时候窗口已经包含了目标串全部字符。很多所谓的难题本质上就是模板加一两个辅助数据结构理解了这一点看着难的题也会变成送分题。4. 链表操作反转链表背后的指针学问4.1 迭代反转三指针法反转链表是链表题型里最基础的敲门砖考验的是对指针引用的理解。题目很直接反转一个单链表。如果对链表熟悉的人几分钟就能写完但里面有一个非常容易踩的坑就是指针顺序。先看代码def reverse_list(head): prev None cur head while cur: next_node cur.next cur.next prev prev cur cur next_node return prev第一步保存next_node是整个操作的关键。当cur.next指向被改成prev以后原来的后继节点就丢了不提前保存就无法继续遍历。面试时我常看到有人卡在这一步说明对“改指针前先留后路”这个原则理解不够深。把这个原则说出来比闷头写更让面试官认可。三个指针的行为可以用一句话概括prev是已反转部分的新头cur是当前正在处理的节点next_node是原链表中还未反转的剩余部分。每次循环把cur的next扭转向后然后三个指针整体往后挪一格。4.2 递归反转理解子问题迭代返回的是新的头节点递归同样要做这件事但思路完全不同。递归解法是深度优先先把“当前节点之后的所有节点”反转好再把当前节点接到已反转部分的尾部。def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_headhead.next.next head是递归版本里最精妙的一行。理解它之前先明确一点递归执行完reverse_list_recursive(head.next)后head.next已经成为反转后链表的最后一个节点。此时把head.next的next指针指向head等于把当前节点接到末尾然后断掉head原来向后的指针。递归最深一层返回的节点就是整个链表的最后一个节点它会在每一层递归中保持为new_head返回最终成为反转后的头节点。递归版本的代码很简洁但面试不推荐优先写因为递归深度等于链表长度链表一旦很长会栈溢出而且讲解起来比迭代复杂。可以在面试中先写出迭代版再补充说“递归版也能实现但存在栈深度风险”体现你的知识面而不过度冒险。4.3 链表题的调试经验链表题在本地调试其实是比较麻烦的事打印链表、构造用例都费劲。我的习惯是凡是链表题先画三个节点把prev、cur、next_node三个指针的变化一步步画出来。画图会暴露很多代码里发现不了的问题尤其是循环结束后指针指向哪里、返回的应该是哪个节点这些画一次就理解了。另外一个常见错误是忘记处理空链表和单节点链表。代码里if not head or not head.next这类判断看似简单但很多人一紧张就漏掉。面试写链表题之前先在心里过一遍这两种情况会稳很多。5. 二叉树遍历递归与迭代的面试必背模板5.1 递归模板三行走天下二叉树遍历是算法面试里的常青树前序、中序、后序、层序几乎必考一种。递归版本的三种遍历代码差异极小只是访问节点的位置不同。前序遍历是先访问当前节点再递归左边和右边中序遍历先递归左边访问节点再递归右边后序遍历先递归左右再访问节点。def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right) def postorder(root): if not root: return [] return postorder(root.left) postorder(root.right) [root.val]这种写法简洁好背但实际面试中递归版本价值不大因为很多人都会写体现不出实力。面试官更愿意看到你能写出非递归版本也就是自己维护栈来实现遍历。这也是区分“背模板”和“真理解”的分水岭。5.2 前序与中序的迭代实现前序遍历的迭代实现基于栈逻辑和递归保持完全一致先访问当前节点再处理左子树和右子树。因为栈是后进先出想先处理左子树就得先把右子树压栈这样右子树会最后被处理符合前序“根左右”的顺序。def preorder_iter(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res中序遍历的迭代法就没这么直接了。中序的顺序是“左根右”所以最开始不能直接访问根节点而要先一直往左走把沿途所有节点全部压栈直到走到最左边然后弹出节点访问再去处理它的右子树。def inorder_iter(root): stack [] res [] cur root while stack or cur: while cur: stack.append(cur) cur cur.left node stack.pop() res.append(node.val) cur node.right return res这段代码是二叉树迭代遍历中最容易忘的版本核心在于外层循环条件必须是while stack or cur不能只写while stack。因为刚开始cur不为空、stack为空这是循环能启动的原因后面cur变成右孩子的过程中stk可能空但cur还有值仍然要继续处理。面试时把这一点讲清楚本身就是加分项。5.3 层序遍历的BFS模板层序遍历按层输出用队列实现每一步从队列取出当前层的节点把它们的下一层节点加进去。关键技巧是每轮循环开始前先记录当前队列长度size然后连续处理size个节点。这个size保证了每次循环恰好处理一层不会混层。from collections import deque def level_order(root): if not root: return [] queue deque([root]) res [] while queue: level [] size len(queue) for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res不要图省事直接用for node in queuePython的for循环不会动态反映队列长度变化。必须固定size不然子节点被加进来后本层循环会连带处理下一层节点层级就乱了。这个细节我在代码评审里反复看到属于高发错误。6. 动态规划入门从状态定义到转移方程6.1 什么时候考虑动态规划动态规划是很多人的噩梦也是面试分级的重要分水岭。判断一道题是否应该用动态规划有几个明显的信号求最值、最优策略、最大化最小化问题可以被划分成重叠子问题当前状态可以由前一个或前几个状态推导出来。典型的例子是斐波那契数列、爬楼梯、打家劫舍、背包问题。动态规划的思想核心只有一句话用状态表示阶段用转移方程连接前后阶段用空间记录已经算过的结果避免重复计算。理解了这个本质你就能识别出很多看起来完全不同的题其实是在考同一件事。6.2 爬楼梯的完整推导爬楼梯是动态规划入门题里最友好的一个。题目是这样每次可以爬1阶或2阶台阶问爬到n阶有多少种不同的方法。先考虑最简单的情况爬到第1阶有1种方法爬到第2阶有2种方法。那么第3阶呢你可以从第2阶跨1步上来也可以从第1阶跨2步上来所以总数等于爬到第1阶的方法加上爬到第2阶的方法。以此类推走到第n阶的方法数等于第n-1阶的方法数加第n-2阶的方法数。这个推理过程就是完整的动态规划推导。定义dp[i]为爬到第i阶的方法数转移方程是dp[i] dp[i-1] dp[i-2]初始条件dp[1]1、dp[2]2。代码实现时其实不需要保留整个dp数组因为状态只依赖前两个值滚动两个变量就够def climb_stairs(n): if n 2: return n prev2, prev1 1, 2 for i in range(3, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1空间优化是面试里的加分点。写出O(n)空间的版本后主动说“这个状态只依赖前两个值可以用滚动变量把空间压到O(1)”面试官会立刻对你刮目相看。6.3 打家劫舍的进阶思考打家劫舍的经典描述是一排房子每间房里有不同金额的现金但相邻两间房不能同时偷问能偷到的最大金额。这道题比爬楼梯高一个维度它引入了“选择”概念。定义dp[i]为偷到第i间房时的最大金额对第i间房有两个选择偷或者不偷。偷的话第i-1间不能偷金额是dp[i-2]nums[i]不偷的话金额是dp[i-1]。取两者较大值。def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] dp [0] * len(nums) dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] max(dp[i - 1], dp[i - 2] nums[i]) return dp[-1]这道题最关键的思维转变是状态定义里的dp[i]和一般“前i项和”不太一样它表示的是“到第i间房为止能获得的最大金额”而不是“必然偷第i间房”。很多新手在这个定义上迷糊导致转移方程写错。把“到当前位置的最优结果”这个状态定义想明白很多DP题就通了。6.4 DP题的四步套路DP题无论难度解题套路固定第一定义状态说清楚dp[i]代表什么含义第二写转移方程说明当前状态怎么由前面状态推出来第三初始化边界处理dp[0]、dp[1]这些起点第四确定遍历顺序从小到大还是从大到小一维多维各不同。面试时按这个顺序讲基本不会乱。常见的错误包括初始化只想着dp[0]忘了dp[1]转移方程里索引越界没判断遍历顺序和状态定义冲突。这些坑靠背是背不掉的只有多写几道题、每题复盘一次才能真正建立起DP的直觉。7. 算法题面试的常见问题与避坑实录7.1 面试现场最容易翻车的三个瞬间第一个翻车瞬间是想得太少就开写写完发现思路错了推倒重来还浪费大量时间。正确做法是写代码前先把思路讲完整就算思路有漏洞面试官也可能帮你纠正而不是直接看你翻车。第二个翻车瞬间是写完代码不说测试直接“写完了”。面试官此时会认为你缺乏工程素养代码即使对了也扣分。第三个翻车瞬间是被问到复杂度时答不上来。复杂度分析不是可选项而是必选项每写完一道题都要能清晰解释。一个很实用的办法是写题时在草稿纸上标出算法涉及的数据结构、时间复杂度和空间复杂度写完直接照着说不会临时卡壳。7.2 小规模测试用例面试官最看重的一步写完代码后手动跑一遍小用例是你展示严谨性的最好机会。不要跑太复杂的用例三个元素就够常规用例、边界用例、特殊用例。比如数组题跑一个空数组和单元素数组链表题跑一个空链表和单节点链表二叉树题跑一个只有左子树的树。手动跑的时候不要只在脑子里抽象过直接一行一行指给面试官看边指边说出变量的值变化。这个动作非常有用能暴露索引越界、空指针、死循环等问题。7.3 刷题阶段怎么练刷题阶段的训练方式直接决定面试水平。不要盲目追求刷题数量我见过刷了300道依旧无法通过面试的人也见过只刷了100道但每道都吃透的人顺利拿到offer。区别在于有没有分类总结。建议按照知识点刷先数组再哈希表再链表再到二叉树每个类别刷完以后统一回顾这一类的通用套路。准备一个自己的模板笔记把常见的模板代码整理下来。比如滑动窗口模板、二叉树迭代遍历模板、双指针模板、DP四步法模板。面试前看这些笔记比重新刷题效率高得多。7.4 复杂度的快速估算面试中被问复杂度是常态我建议形成一套固定的分析方法循环嵌套决定时间复杂度的量级递归看递归树的高度和分叉数哈希表操作平均O(1)排序O(nlogn)。空间复杂度主要看额外数据结构用了哈希表就是O(n)用了栈做二叉迭代遍历最坏O(h)h为树高。下面这张表总结了本文提到的题型复杂度方便面试前快速过一遍题型典型解法时间复杂度空间复杂度两数之和哈希表O(n)O(n)三数之和排序双指针O(n^2)O(logn)到O(n)无重复字符最长子串滑动窗口O(n)O(n)反转链表迭代三指针O(n)O(1)二叉树前序/中序栈迭代O(n)O(h)二叉树层序队列BFSO(n)O(n)爬楼梯滚动变量DPO(n)O(1)打家劫舍动态规划O(n)O(1)可优化我自己的经验是复杂度分析不是额外负担而是检验你是否真正理解算法的试金石。如果你说不出复杂度往往说明你对算法的每一步执行还不够清晰。把这篇文章里的每个模板代码都亲手敲一遍再把复杂度讲给自己听效果远比堆刷题量要好。面试真正拼的不是见过多少题而是面对新题时能否快速定位考点、套用模板、排除边界。这些能力没有任何捷径只能在分类练习和复盘总结中慢慢积累。