1. 二维数组中的查找为什么“右上角出发”比暴力扫描更有面试价值1.1 题目描述与最笨的解法剑指Offer里数组与矩阵专题的第一道题通常都是“二维数组中的查找”。我给自家学员讲的时候喜欢先把原题贴出来在一个二维数组中每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序请完成一个函数输入这样一个二维数组和一个整数判断数组中是否含有该整数。很多第一次刷题的人第一反应是双重循环暴力扫描这当然能过但面试官让你写这道题图的不是你两分钟写完一个O(n²)的遍历而是想看你有没有识别出“行列同时递增”这个特殊结构的眼光。我见过不少候选人一上来就写嵌套for写完还觉得挺稳结果面试官一句“你能不用两层循环吗”就懵了。这里要先建立第一个认知凡是题目里给出“每一行递增、每一列递增”这种约束一定不是白给的它在提示你数据具有某种局部有序性可以做到比全量扫描更快的查找。暴力解不是不能用而是它浪费了题目给的核心条件相当于把一张藏宝图当成白纸擦桌子。1.2 右上角坐标的意义同时淘汰一行和一列解法是选右上角或者左下角作为起点这不算什么新鲜结论但很多人只知道“用右上角”并不知道为什么是右上角。我换个方式解释右上角的元素拥有双重身份——它是它所在行的最大值同时是它所在列的最小值。这个双重身份带来的好处是拿目标值和它比较一次无论结果是大于还是小于你都能确定性地淘汰一整行或一整列。具体来说从右上角开始如果目标值小于当前元素那目标值不可能出现在当前这一列因为这一列从上到下是递增的右上角已经是这列最小的了所以整列可以直接丢弃指针左移如果目标值大于当前元素那目标值不可能出现在当前这一行因为当前元素是这行最大的所以整行丢弃指针下移。每比较一次搜索范围就缩小一行或一列最坏情况下从右上角走到左下角步数等于行数加列数时间复杂度O(mn)。这种“一次比较淘汰一大片”的思路比二分更灵活。二分要求数据在一维上有严格单调性而这里矩阵只在行和列两个方向上分别单调单独拿哪一行出来二分也能做但那样每一行都二分一次就是O(m·log n)了不如O(mn)的右上角扫描。更关键的是这种“利用角点特性同时压缩两个维度”的思想在后面的矩阵题里会反复出现。1.3 参考实现与测试用例下面是Java版本的实现我把核心逻辑写在主循环里边界判断放前面。实际面试的时候这样写最不容易漏判空数组。public boolean findNumberIn2DArray(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int rows matrix.length; int cols matrix[0].length; int row 0; int col cols - 1; while (row rows col 0) { int cur matrix[row][col]; if (cur target) { return true; } else if (cur target) { col--; } else { row; } } return false; }这里有两个容易踩的坑第一是matrix[0].length的判断如果传入的是空数组占位比如new int[0][0]不判断matrix[0]就会抛异常第二是while条件的顺序row rows col 0很多人写成row rows一旦目标值比矩阵最小值还小row会走到rows才停这时候matrix[row][col]已经越界了。我平时让读者自测会用这几组用例空数组、只有一行的矩阵、只有一列矩阵、目标值在左上角或右下角、目标值不在矩阵范围内但介于矩阵最大最小值之间、矩阵里全是重复值。这几组都能跑通基本就不会在边界上出问题。1.4 面试追问左下角、对角线、或者降维处理面试官如果继续深挖常见的问题是“左下角可不可以”。左下角同样可以因为左下角是所在行的最小值、所在列的最大值比较一次同样能淘汰一行或一列。左上角和右下角不行因为左上角是行最小也是列最小比它小无法判断方向比它大则两个方向都可能。还有一个变体是“矩阵按对角线递增问怎么优化”此时右上角扫描仍然适用但对角线本身也可以二分面试里如果被问到“还可以更快吗”可以说先沿对角线二分定位到某条对角线附近的子矩阵再继续右上角扫描这个思路能体现出你理解数据结构的程度。这道题本身不难但它奠定了这个专题的第一块基石识别特殊有序结构利用角点性质做定向搜索。后面很多题包括矩阵中找第K小、搜索二维矩阵都是在这个基础上改的所以我把这题放在整个系列的开头来讲。2. 旋转数组的最小数字二分的边界到底该信谁2.1 题目背景与常见的错误二分第二道必须掌握的题是“旋转数组的最小数字”。题目是这样的把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个递增排序的数组的一个旋转输出旋转数组的最小元素。比如[3,4,5,1,2]是[1,2,3,4,5]的一个旋转最小值是1。这题第一眼让人想直接遍历找最小值但面试官给你一个接近有序的数组目的就是考二分变形。我见过太多人在这一步翻车套路很一致拿到题发现是二分就刻板地用mid和left比较结果在[3,4,5,1,2]这类例子里直接死循环或者退回暴力扫描。先说说为什么不能简单地和left比较。在普通升序数组里nums[mid] nums[left] 说明目标在左半段大于等于则在右半段这个逻辑成立是因为整个数组严格递增。但旋转数组在某个位置断开了最大值和最小值相邻我们没法用普通二分的“拿中间值和左边界比大小”来定位。你要找的其实是那个“下降沿”附近的最小值而这个下降沿和左边界没有任何可靠的相对关系。2.2 mid与high比较的完整推导正确的做法是让mid和high比较。为什么是和high不是和left因为旋转数组有一个特性最小值一定位于“无序断点”的右半部分附近如果我们把搜索区间定义为[low, high]那么与右边界high比较能更好地识别出断点的位置。先假设数组没有重复元素比如[4,5,6,1,2,3]mid指向6nums[mid] nums[high]说明断点在mid的右侧也就是最小值在右半边所以low移到mid1。反之若nums[mid] nums[high]说明从mid到high这段是连续递增的最小值不可能在这段里high移到mid。这里有个很微妙的点为什么等于的情况要归到“high mid”那边以及为什么用high而不用low本质上是因为我们假设数组旋转过一次最小值右边的所有元素都不会小于等于它而mid和high相等时无法判断断点在哪一侧需要退化为线性收缩。2.3 重复元素时的收缩策略如果数组里有重复元素比如[2,2,2,0,2,2]这个例子里nums[mid]等于nums[high]你没法判断最小值在左还是在右。这时候标准做法是high--把右边界往左收缩一位重新比较。注意这不是简单的跳过而是通过缩小右边界来恢复“mid和high可比较”的条件。很多教材直接把这个规则作为结论写出来但面试里我建议你主动说明为什么可以缩。原因是当nums[mid] nums[high]时即使high位置就是最小值我们把high向左移动一位后最小值仍在区间[low, high]内不会丢解。所以这种收缩是安全的。如果面试官追问“有没有可能缩掉真正的解”你就可以举这个例子high位置等于mid值而mid位置又大于等于最小值所以把high缩到high-1不影响最终最小值的存在位置。写代码时只要记住三点优先用mid和high比较等于时high--除以2的时候用low (high - low) / 2防止大数溢出。下面是核心片段public int minNumberInRotateArray(int[] nums) { if (nums null || nums.length 0) { return 0; } int low 0; int high nums.length - 1; while (low high) { int mid low (high - low) / 2; if (nums[mid] nums[high]) { low mid 1; } else if (nums[mid] nums[high]) { high mid; } else { high--; } } return nums[low]; }2.4 这道题背后测的“边界意识”这题真正的考点其实不是算法本身而是候选人有没有“边界意识”。普通二分写顺手了最容易犯的错是循环条件写成low high导致死循环或者把high mid写成high mid - 1直接跳过最小值。我自己刷这题的时候反复测过好几种输入[1,2,3,4,5]这种没旋转的数组系统也要求它返回1[1]这种单元素数组[1,1,1,1]这种全重复数组。你会发现全部转成上面这段代码都能通就是因为mid和high的比较逻辑在“完全递增”和“完全重复”的场景下同样成立。面试时如果时间紧张至少把这些用例过一遍再交卷。这道题更值得记住的是那个思维转变二分法的本质不是“跟left比”而是“找一种能不断缩小搜索空间的比较对象”。普通数组拿left比是因为整个区间有序旋转数组拿high比是因为最小值被“挤”到了右侧序列里理解这个语境比背下low和high的更新规则重要一百倍。3. 数组重排与指针移动奇数前偶数后的两种写法3.1 基本题快慢指针一次遍历“调整数组顺序使奇数位于偶数前面”是剑指Offer里很经典的指针移动题。题目本身不复杂输入一个整数数组实现一个函数来调整该数组中数字的顺序使得所有奇数位于数组的前半部分所有偶数位于数组的后半部分。多数人第一次的思路是开个新数组遍历一遍把奇数放前面、偶数放后面时间复杂度O(n)、空间复杂度O(n)。但面试官通常希望你用O(1)额外空间原地完成这就引出了快慢指针或者首尾指针的思路。最直观的写法是首尾双指针左指针从左往右找偶数右指针从右往左找奇数找到就交换两指针相遇时结束。这个思路实现起来十来行人人都能写。但我面试的时候更推荐练一手快慢指针的写法一个指针负责遍历另一个指针指向下一个奇数应该放的位置遇到奇数就把它换到前面去。为什么推荐快慢指针因为它有一个额外好处如果题目要求“所有奇数之间、所有偶数之间的相对顺序不变”首尾交换法做不到而快慢指针配合类似插入排序的前移操作可以做到。这是个非常容易被追问的点。3.2 进阶条件保持相对顺序原版剑指Offer其实没有强制要求稳定但很多面试官会随口加一句“奇数和偶数的内部相对顺序要保持一致”这时候首尾交换就挂了。比如[1,2,4,3,5]首尾交换后变成[1,5,3,4,2]奇数内部的1、3、5变成了1、5、3相对顺序已经被打乱。要保持稳定性最简单的方案是额外数组遍历原数组把奇数按顺序收集一遍再收集一遍偶数最后拼回去。如果你硬要原地稳定可以用冒泡式的前移每遇到一个奇数就把它一步步换到前面最坏O(n²)只适合在讨论复杂度时说明不建议面试时写。我给读者的建议是面试现场先确认清楚“稳不稳定”如果没明确说明默认做不稳定版本就好因为首尾交换更简单也更快。如果面试官要求稳定直接坦白用辅助数组换空间比在产品代码里追求一个极致的原地算法更符合工程直觉。3.3 “指针数组”相关笔试题的常见变体热搜词里频繁出现的“指针数组”在这个专题里通常不是指语言层面的那个语法概念而是指一类“通过指针/索引移动来重排数组”的题目。除了奇偶分离还有几个经典变体把负数移到正数前面同样双指针但注意0放在哪边要提前和面试官确认。把0移到数组末尾这是LeetCode 283移动零很多人会写错成“把所有非零前移后补零”实际更好的做法是快慢指针覆盖前移。按某个自定义比较器重排本质上可以统一成一个模板——定义“哪种元素应该靠前”然后用分区思想做。这些题的共同点是它们并不追求复杂的算法而是考察你对指针边界、交换顺序、以及“分类标准”的敏感度。数组重排类的题目里最常见的研究生错误是在交换后忘记移动指针导致同一个元素被重复处理还有就是在负数/奇数的判断条件上用了不统一的等号。我在实际带项目的时候也发现这种“按条件把数组区分成两段”的思路直接对应着实际工程里的分区逻辑比如把待重试的任务和成功任务分开、把白名单流量和黑名单流量分开。所以别小看这道题它确实是高频笔试题也是工程里每天都在用的基础操作。4. 多数元素与最大子数组两个看似无关实则同源的O(n)算法4.1 出现次数超过一半的数字摩尔投票法的直觉“数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。”这是剑指Offer里一道经典题LeetCode对应的是169题。很多人第一反应是哈希表统计O(n)时间和O(n)空间这当然能解。但这道题的最优解是摩尔投票算法空间复杂度O(1)。它的核心思想可以类比成“打仗消耗”候选数字和当前票数遇到相同数字就加一票遇到不同数字就减一票票数减到零就换候选者。因为目标数字出现次数超过一半所以即使中间有消耗和替换最终留下的候选者一定是那个多数元素。很多初学者不理解“为什么最后留下的就一定是答案”我来解释得更细一点。假设数组中某个元素出现次数大于n/2其他所有元素加起来都不到n/2。那么这个元素每和一个不同元素配对消耗一次也一定会有剩余因为它的数量大于其他所有元素的总和。所以无论怎么消耗最后胜出的候选者只能是它。但要注意一个坑摩尔投票法只能保证“如果有超过一半的数最终候选者是它”它本身不能证明候选者真的超过一半。所以原题如果没保证“一定存在”你还需要遍历一次统计候选者出现次数确认它确实大于n/2。这个二次验证步骤我在面试里几乎必加不然碰到没有合法答案的用例就会返回错误结果。4.2 连续子数组最大和Kadane算法的状态定义“连续子数组的最大和”也是数组专题绕不开的题。题目输入一个整型数组数组里有正数也有负数数组中的一个或连续多个整数组成一个子数组求所有子数组的和的最大值。这题第一眼可能想用暴力枚举所有子数组O(n²)或者O(n³)。但面试真题要求O(n)。标准答案是Kadane算法简单说就是动态规划的状态压缩版。我讲这道题喜欢让学生先定义一个状态dp[i]表示以第i个元素结尾的连续子数组的最大和。那么状态转移只有两种选择——要么把nums[i]接到前一个子数组后面要么从nums[i]重新开始一个新的子数组。写成公式就是dp[i] max(dp[i-1] nums[i], nums[i])。再进一步dp[i]只依赖dp[i-1]所以用一个变量滚动更新就行连数组都不用开。实际写的时候有个很多人忽略的细节初始值不能设成0要设成nums[0]或者Integer.MIN_VALUE。因为如果数组全为负数设0会导致结果恒为0正确答案应该是最大的那个负数。这个坑在LeetCode 53上几乎天天都有人踩。这题我强烈建议你自己推导一遍状态转移而不是背代码。因为“以谁结尾”这个角度后面解最长递增子序列、乘积最大子数组都能复用状态设计的习惯就这么建立的。4.3 同构数组题哈希映射双射关系的一个典型陷阱热搜词里有一条“是否同构有两个长度为n的数组如果存在一个整数满足且保持数组”——这正是LeetCode 205同构字符串的数组版本。题目可以描述成给定两个长度相同的数组a和b判断它们是否同构也就是说a中每个位置上的数字是否可以一一映射到b中对应位置上的数字且这个映射是双射。剑指Offer原书没有这道题但因为LeetCode必刷它经常出现在面试前几轮的热身题里。同构的核心要求是一个来自a的值只能映射到一个来自b的值反过来也一样。你不能出现a里两个不同位置都映射到b里同一个值也不能出现a里同一个值映射到b里两个不同值。具体实现用两个哈希表分别记录a-b和b-a的双向映射。遍历时如果映射已存在且不一致直接返回false否则建立映射。很多人在写单向映射时漏了反向校验导致[1,2]和[2,1]这类对称场景被误判为同构。这个小节看起来和前面的多数元素、最大子数组风格不同但它同样属于“用哈希表做数值关系校验”的范畴是数组题里最容易被快速考到的简单题。我把它放这里是想提醒你数组专题不只考排序查找还大量考映射和状态关系跟着LeetCode热榜刷这类题迟早会碰到。5. 矩阵遍历与回溯顺时针打印和矩阵中的路径5.1 顺时针打印矩阵用边界收缩代替方向判断进入矩阵部分第一道高频题是“顺时针打印矩阵”。题目要求输入一个矩阵按照从外向里顺时针打印每一个元素。这道题几乎每次面试都会有人拿出来因为代码量适中边界条件又极多特别适合考察代码完整性。我的解法思路是“边界收缩”不做复杂的方向切换。维护四个变量top、bottom、left、right每打印完一圈就收缩一圈。每次先从左到右打印top行然后top接着从上到下打印right列然后right--如果top bottom从右到左打印bottom行再bottom--如果left right从下到上打印left列再left。很多人第一次写会漏掉后面两个if判断导致只有一行或只有一列的矩阵打印出多余元素。实际测试时务必加[1,2,3]这种单行矩阵和[[1],[2],[3]]这种单列矩阵它们最能暴露边界条件不完整的问题。这道题还有一个高频变体要求按“之字形”打印矩阵。思路仍然是边界收缩只是在奇数层时把从左到右的打印改成从右到左本质没变但面试时临场推反方向容易晕建议先画一个3×3的矩阵把指针每走一格的位置变化写在纸上再动手写代码。5.2 矩阵中的路径DFS回溯的“状态恢复”细节另一道矩阵高频题是“矩阵中的路径”原题是判断在一个字符矩阵中是否存在一条包含某字符串所有字符的路径路径可以从任意格子出发每一步可以上下左右移动一格不能重复经过格子。这和LeetCode 79单词搜索基本一致。这种题的核心套路是DFS加回溯。从每个格子出发尝试匹配字符串四个方向递归搜索匹配失败就回退。这里最容易出错的地方是“状态恢复”进入一个格子时把这个格子标记为已访问返回前要把标记擦掉否则后续分支无法再次使用这个格子。很多读者问我为什么撤销标记是必须的。举个例子矩阵里有一个“A”和一个“B”你要找“ABA”这条路径。如果第一次从A出发向右走到B再想回到A但这个A已经被标记为已访问不擦除的话就直接返回false了。可实际上路径是可以重复利用起点格子的吗要注意题目要求“不能重复经过格子”但路径往回走的那个格子并不是重复经过而是从B回到起点A起点A在进入B前已经访问过了如果保留标记这个回退就会被禁止。所以撤销标记的本质是让回溯路径上的祖先节点重新变为可用状态。写DFS的时候我推荐的模板是先判断边界和字符匹配再做访问标记递归四个方向最后撤销标记并返回结果。递归终止条件就是当前字符索引等于字符串长度减一。深度优先搜索在LeetCode上通常能用但要注意递归栈的深度如果矩阵特别大可以跟面试官讨论用显式栈迭代版本。5.3 进阶链接用矩阵快速幂优化递推问题矩阵这个方向除了遍历和搜索还有一个面试中经常作为“延伸题”出现的方向矩阵快速幂。热搜词里的“矩阵快速幂”“矩阵·快速幂算法”说的就是这个。剑指Offer里最出名的相关题是“斐波那契数列”——虽然原题用动态规划就能解但面试官进阶一问往往是“能不能用O(log n)算第n项”。这时候把递推关系写成矩阵形式状态向量[F(n), F(n-1)]可以由矩阵[[1,1],[1,0]]乘以前一个状态向量得到求第n项就等价于求这个矩阵的n次幂。矩阵快速幂的思路和整数快速幂完全一致把指数拆成二进制用“幂的平方”累积结果只是底数从整数变成矩阵。写的时候注意矩阵乘法函数别写错循环顺序三重循环里i、j、k的顺序要固定。这道题我在准备面试阶段至少手写了五遍因为矩阵乘法下标一错调试起来非常痛苦。我当时学矩阵快速幂的感受是它看起来像数学玩具其实在状态转移方程的时间复杂度优化上有实际价值。比如有些动态规划题的状态转移是线性的就可以用矩阵加速从O(n)降到O(log n)。这套思路想通了再看“矩阵求逆”“特征值分解”这些线代名词就不会觉得高不可攀算法题里能用到的只是其中很小一部分。6. 数组和矩阵题的工程素养越界、空值、极端输入与测试习惯6.1 最容易翻车的五个位置数组和矩阵题目虽然看起来简单但在笔试环境下翻车率一点都不低。我总结了五个最容易出问题的地方每次刷题前过一遍能少踩很多坑第一个是空数组和null的判断。Joseph很多题默认输入非空但牛客网的测试用例经常给你灌null。最好在函数开头就写统一判空逻辑不要等用到matrix[0]时才报错。第二个是二维数组的matrix[0].length。有些题传进来的是int[0][0]直接取matrix[0]会抛异常判断顺序应该是matrix null、matrix.length 0、matrix[0].length 0一个都不能少。第三个是索引越界。尤其矩阵DFS和旋转数组二分row 1、col - 1这类操作放在边界判断之前还是之后顺序写反了就是一个ArrayIndexOutOfBoundsException。第四个是增量溢出的问题。比如旋转数组里求mid写(left right) / 2如果数组长度接近int最大值leftright会溢出建议统一写left (right - left) / 2。第五个是返回值类型不匹配。原题说“没有这样的数返回什么”一定先看题比如旋转数组最小数字的题目常常默认数组非空返回0或其他占位值就不行。这些看似琐碎的细节在实际笔试里是真真切切能拉开差距的地方。我在公司帮忙筛简历的时候看过不少候选人算法思路完全正确但就是挂在边界case上最后系统判一个用例不过整题零分特别可惜。6.2 一个完整的测试用例清单刷题时我建议你准备一套“通用测试清单”对大部分数组和矩阵题都能用空数组、null输入只有单个元素的数组全部元素相同的数组已经有序或完全逆序的数组目标值在数组两端的情况目标值在数组中但重复多次负数、零、正数混合矩阵只有一行或一列矩阵行数和列数不等长方形矩阵这套清单看着简单但真能覆盖绝大多数边界问题。我在练题阶段每写完一个解法就强制自己跑一遍清单时间久了就会形成肌肉记忆面试时也会先问清楚输入是否保证合法而不是默认一个完美世界。6.3 我个人建议的刷题顺序和节奏最后聊一点比较私人的经验。如果你是刚开始准备算法面试不要直接一头扎进LeetCode随机刷。先按专题过一遍剑指Offer数组和矩阵就是最好的起点因为后面很多链表题、树题最后都会转化为数组的处理逻辑。我说个真实感受树的层序遍历结果是个数组图的邻接矩阵用二维数组存二分查找优化到最后也是在数组上移动指针。数组底子如果打得不牢后面学什么都会觉得飘。我自己的节奏是每天三到四道题先不看题解硬想15分钟想不出来再看思路但看完以后合上答案自己完整写一遍第二天再把这些题复现一遍。这个“第二天重写”的步骤很多人不愿意做但它恰恰是最关键的。因为背出来的解法和真正内化的解法隔一个星期你自己就能分辨出来。如果你已经刷过一遍基础题想进阶可以试试把每道题的多种解法都写一遍并且算清楚各自的时空复杂度。比如二维数组查找既写暴力扫描又写右上角扫描再写每行二分比较它们在不同数据规模下的差异。这个过程比单纯刷题数量更能训练工程判断力——因为真实工作中你选哪套方案不完全取决于“能不能跑”还要看数据量、边界情况、可维护性这些在面试深度追问时最容易被看到。
1. 二维数组中的查找为什么“右上角出发”比暴力扫描更有面试价值1.1 题目描述与最笨的解法剑指Offer里数组与矩阵专题的第一道题通常都是“二维数组中的查找”。我给自家学员讲的时候喜欢先把原题贴出来在一个二维数组中每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序请完成一个函数输入这样一个二维数组和一个整数判断数组中是否含有该整数。很多第一次刷题的人第一反应是双重循环暴力扫描这当然能过但面试官让你写这道题图的不是你两分钟写完一个O(n²)的遍历而是想看你有没有识别出“行列同时递增”这个特殊结构的眼光。我见过不少候选人一上来就写嵌套for写完还觉得挺稳结果面试官一句“你能不用两层循环吗”就懵了。这里要先建立第一个认知凡是题目里给出“每一行递增、每一列递增”这种约束一定不是白给的它在提示你数据具有某种局部有序性可以做到比全量扫描更快的查找。暴力解不是不能用而是它浪费了题目给的核心条件相当于把一张藏宝图当成白纸擦桌子。1.2 右上角坐标的意义同时淘汰一行和一列解法是选右上角或者左下角作为起点这不算什么新鲜结论但很多人只知道“用右上角”并不知道为什么是右上角。我换个方式解释右上角的元素拥有双重身份——它是它所在行的最大值同时是它所在列的最小值。这个双重身份带来的好处是拿目标值和它比较一次无论结果是大于还是小于你都能确定性地淘汰一整行或一整列。具体来说从右上角开始如果目标值小于当前元素那目标值不可能出现在当前这一列因为这一列从上到下是递增的右上角已经是这列最小的了所以整列可以直接丢弃指针左移如果目标值大于当前元素那目标值不可能出现在当前这一行因为当前元素是这行最大的所以整行丢弃指针下移。每比较一次搜索范围就缩小一行或一列最坏情况下从右上角走到左下角步数等于行数加列数时间复杂度O(mn)。这种“一次比较淘汰一大片”的思路比二分更灵活。二分要求数据在一维上有严格单调性而这里矩阵只在行和列两个方向上分别单调单独拿哪一行出来二分也能做但那样每一行都二分一次就是O(m·log n)了不如O(mn)的右上角扫描。更关键的是这种“利用角点特性同时压缩两个维度”的思想在后面的矩阵题里会反复出现。1.3 参考实现与测试用例下面是Java版本的实现我把核心逻辑写在主循环里边界判断放前面。实际面试的时候这样写最不容易漏判空数组。public boolean findNumberIn2DArray(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int rows matrix.length; int cols matrix[0].length; int row 0; int col cols - 1; while (row rows col 0) { int cur matrix[row][col]; if (cur target) { return true; } else if (cur target) { col--; } else { row; } } return false; }这里有两个容易踩的坑第一是matrix[0].length的判断如果传入的是空数组占位比如new int[0][0]不判断matrix[0]就会抛异常第二是while条件的顺序row rows col 0很多人写成row rows一旦目标值比矩阵最小值还小row会走到rows才停这时候matrix[row][col]已经越界了。我平时让读者自测会用这几组用例空数组、只有一行的矩阵、只有一列矩阵、目标值在左上角或右下角、目标值不在矩阵范围内但介于矩阵最大最小值之间、矩阵里全是重复值。这几组都能跑通基本就不会在边界上出问题。1.4 面试追问左下角、对角线、或者降维处理面试官如果继续深挖常见的问题是“左下角可不可以”。左下角同样可以因为左下角是所在行的最小值、所在列的最大值比较一次同样能淘汰一行或一列。左上角和右下角不行因为左上角是行最小也是列最小比它小无法判断方向比它大则两个方向都可能。还有一个变体是“矩阵按对角线递增问怎么优化”此时右上角扫描仍然适用但对角线本身也可以二分面试里如果被问到“还可以更快吗”可以说先沿对角线二分定位到某条对角线附近的子矩阵再继续右上角扫描这个思路能体现出你理解数据结构的程度。这道题本身不难但它奠定了这个专题的第一块基石识别特殊有序结构利用角点性质做定向搜索。后面很多题包括矩阵中找第K小、搜索二维矩阵都是在这个基础上改的所以我把这题放在整个系列的开头来讲。2. 旋转数组的最小数字二分的边界到底该信谁2.1 题目背景与常见的错误二分第二道必须掌握的题是“旋转数组的最小数字”。题目是这样的把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个递增排序的数组的一个旋转输出旋转数组的最小元素。比如[3,4,5,1,2]是[1,2,3,4,5]的一个旋转最小值是1。这题第一眼让人想直接遍历找最小值但面试官给你一个接近有序的数组目的就是考二分变形。我见过太多人在这一步翻车套路很一致拿到题发现是二分就刻板地用mid和left比较结果在[3,4,5,1,2]这类例子里直接死循环或者退回暴力扫描。先说说为什么不能简单地和left比较。在普通升序数组里nums[mid] nums[left] 说明目标在左半段大于等于则在右半段这个逻辑成立是因为整个数组严格递增。但旋转数组在某个位置断开了最大值和最小值相邻我们没法用普通二分的“拿中间值和左边界比大小”来定位。你要找的其实是那个“下降沿”附近的最小值而这个下降沿和左边界没有任何可靠的相对关系。2.2 mid与high比较的完整推导正确的做法是让mid和high比较。为什么是和high不是和left因为旋转数组有一个特性最小值一定位于“无序断点”的右半部分附近如果我们把搜索区间定义为[low, high]那么与右边界high比较能更好地识别出断点的位置。先假设数组没有重复元素比如[4,5,6,1,2,3]mid指向6nums[mid] nums[high]说明断点在mid的右侧也就是最小值在右半边所以low移到mid1。反之若nums[mid] nums[high]说明从mid到high这段是连续递增的最小值不可能在这段里high移到mid。这里有个很微妙的点为什么等于的情况要归到“high mid”那边以及为什么用high而不用low本质上是因为我们假设数组旋转过一次最小值右边的所有元素都不会小于等于它而mid和high相等时无法判断断点在哪一侧需要退化为线性收缩。2.3 重复元素时的收缩策略如果数组里有重复元素比如[2,2,2,0,2,2]这个例子里nums[mid]等于nums[high]你没法判断最小值在左还是在右。这时候标准做法是high--把右边界往左收缩一位重新比较。注意这不是简单的跳过而是通过缩小右边界来恢复“mid和high可比较”的条件。很多教材直接把这个规则作为结论写出来但面试里我建议你主动说明为什么可以缩。原因是当nums[mid] nums[high]时即使high位置就是最小值我们把high向左移动一位后最小值仍在区间[low, high]内不会丢解。所以这种收缩是安全的。如果面试官追问“有没有可能缩掉真正的解”你就可以举这个例子high位置等于mid值而mid位置又大于等于最小值所以把high缩到high-1不影响最终最小值的存在位置。写代码时只要记住三点优先用mid和high比较等于时high--除以2的时候用low (high - low) / 2防止大数溢出。下面是核心片段public int minNumberInRotateArray(int[] nums) { if (nums null || nums.length 0) { return 0; } int low 0; int high nums.length - 1; while (low high) { int mid low (high - low) / 2; if (nums[mid] nums[high]) { low mid 1; } else if (nums[mid] nums[high]) { high mid; } else { high--; } } return nums[low]; }2.4 这道题背后测的“边界意识”这题真正的考点其实不是算法本身而是候选人有没有“边界意识”。普通二分写顺手了最容易犯的错是循环条件写成low high导致死循环或者把high mid写成high mid - 1直接跳过最小值。我自己刷这题的时候反复测过好几种输入[1,2,3,4,5]这种没旋转的数组系统也要求它返回1[1]这种单元素数组[1,1,1,1]这种全重复数组。你会发现全部转成上面这段代码都能通就是因为mid和high的比较逻辑在“完全递增”和“完全重复”的场景下同样成立。面试时如果时间紧张至少把这些用例过一遍再交卷。这道题更值得记住的是那个思维转变二分法的本质不是“跟left比”而是“找一种能不断缩小搜索空间的比较对象”。普通数组拿left比是因为整个区间有序旋转数组拿high比是因为最小值被“挤”到了右侧序列里理解这个语境比背下low和high的更新规则重要一百倍。3. 数组重排与指针移动奇数前偶数后的两种写法3.1 基本题快慢指针一次遍历“调整数组顺序使奇数位于偶数前面”是剑指Offer里很经典的指针移动题。题目本身不复杂输入一个整数数组实现一个函数来调整该数组中数字的顺序使得所有奇数位于数组的前半部分所有偶数位于数组的后半部分。多数人第一次的思路是开个新数组遍历一遍把奇数放前面、偶数放后面时间复杂度O(n)、空间复杂度O(n)。但面试官通常希望你用O(1)额外空间原地完成这就引出了快慢指针或者首尾指针的思路。最直观的写法是首尾双指针左指针从左往右找偶数右指针从右往左找奇数找到就交换两指针相遇时结束。这个思路实现起来十来行人人都能写。但我面试的时候更推荐练一手快慢指针的写法一个指针负责遍历另一个指针指向下一个奇数应该放的位置遇到奇数就把它换到前面去。为什么推荐快慢指针因为它有一个额外好处如果题目要求“所有奇数之间、所有偶数之间的相对顺序不变”首尾交换法做不到而快慢指针配合类似插入排序的前移操作可以做到。这是个非常容易被追问的点。3.2 进阶条件保持相对顺序原版剑指Offer其实没有强制要求稳定但很多面试官会随口加一句“奇数和偶数的内部相对顺序要保持一致”这时候首尾交换就挂了。比如[1,2,4,3,5]首尾交换后变成[1,5,3,4,2]奇数内部的1、3、5变成了1、5、3相对顺序已经被打乱。要保持稳定性最简单的方案是额外数组遍历原数组把奇数按顺序收集一遍再收集一遍偶数最后拼回去。如果你硬要原地稳定可以用冒泡式的前移每遇到一个奇数就把它一步步换到前面最坏O(n²)只适合在讨论复杂度时说明不建议面试时写。我给读者的建议是面试现场先确认清楚“稳不稳定”如果没明确说明默认做不稳定版本就好因为首尾交换更简单也更快。如果面试官要求稳定直接坦白用辅助数组换空间比在产品代码里追求一个极致的原地算法更符合工程直觉。3.3 “指针数组”相关笔试题的常见变体热搜词里频繁出现的“指针数组”在这个专题里通常不是指语言层面的那个语法概念而是指一类“通过指针/索引移动来重排数组”的题目。除了奇偶分离还有几个经典变体把负数移到正数前面同样双指针但注意0放在哪边要提前和面试官确认。把0移到数组末尾这是LeetCode 283移动零很多人会写错成“把所有非零前移后补零”实际更好的做法是快慢指针覆盖前移。按某个自定义比较器重排本质上可以统一成一个模板——定义“哪种元素应该靠前”然后用分区思想做。这些题的共同点是它们并不追求复杂的算法而是考察你对指针边界、交换顺序、以及“分类标准”的敏感度。数组重排类的题目里最常见的研究生错误是在交换后忘记移动指针导致同一个元素被重复处理还有就是在负数/奇数的判断条件上用了不统一的等号。我在实际带项目的时候也发现这种“按条件把数组区分成两段”的思路直接对应着实际工程里的分区逻辑比如把待重试的任务和成功任务分开、把白名单流量和黑名单流量分开。所以别小看这道题它确实是高频笔试题也是工程里每天都在用的基础操作。4. 多数元素与最大子数组两个看似无关实则同源的O(n)算法4.1 出现次数超过一半的数字摩尔投票法的直觉“数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。”这是剑指Offer里一道经典题LeetCode对应的是169题。很多人第一反应是哈希表统计O(n)时间和O(n)空间这当然能解。但这道题的最优解是摩尔投票算法空间复杂度O(1)。它的核心思想可以类比成“打仗消耗”候选数字和当前票数遇到相同数字就加一票遇到不同数字就减一票票数减到零就换候选者。因为目标数字出现次数超过一半所以即使中间有消耗和替换最终留下的候选者一定是那个多数元素。很多初学者不理解“为什么最后留下的就一定是答案”我来解释得更细一点。假设数组中某个元素出现次数大于n/2其他所有元素加起来都不到n/2。那么这个元素每和一个不同元素配对消耗一次也一定会有剩余因为它的数量大于其他所有元素的总和。所以无论怎么消耗最后胜出的候选者只能是它。但要注意一个坑摩尔投票法只能保证“如果有超过一半的数最终候选者是它”它本身不能证明候选者真的超过一半。所以原题如果没保证“一定存在”你还需要遍历一次统计候选者出现次数确认它确实大于n/2。这个二次验证步骤我在面试里几乎必加不然碰到没有合法答案的用例就会返回错误结果。4.2 连续子数组最大和Kadane算法的状态定义“连续子数组的最大和”也是数组专题绕不开的题。题目输入一个整型数组数组里有正数也有负数数组中的一个或连续多个整数组成一个子数组求所有子数组的和的最大值。这题第一眼可能想用暴力枚举所有子数组O(n²)或者O(n³)。但面试真题要求O(n)。标准答案是Kadane算法简单说就是动态规划的状态压缩版。我讲这道题喜欢让学生先定义一个状态dp[i]表示以第i个元素结尾的连续子数组的最大和。那么状态转移只有两种选择——要么把nums[i]接到前一个子数组后面要么从nums[i]重新开始一个新的子数组。写成公式就是dp[i] max(dp[i-1] nums[i], nums[i])。再进一步dp[i]只依赖dp[i-1]所以用一个变量滚动更新就行连数组都不用开。实际写的时候有个很多人忽略的细节初始值不能设成0要设成nums[0]或者Integer.MIN_VALUE。因为如果数组全为负数设0会导致结果恒为0正确答案应该是最大的那个负数。这个坑在LeetCode 53上几乎天天都有人踩。这题我强烈建议你自己推导一遍状态转移而不是背代码。因为“以谁结尾”这个角度后面解最长递增子序列、乘积最大子数组都能复用状态设计的习惯就这么建立的。4.3 同构数组题哈希映射双射关系的一个典型陷阱热搜词里有一条“是否同构有两个长度为n的数组如果存在一个整数满足且保持数组”——这正是LeetCode 205同构字符串的数组版本。题目可以描述成给定两个长度相同的数组a和b判断它们是否同构也就是说a中每个位置上的数字是否可以一一映射到b中对应位置上的数字且这个映射是双射。剑指Offer原书没有这道题但因为LeetCode必刷它经常出现在面试前几轮的热身题里。同构的核心要求是一个来自a的值只能映射到一个来自b的值反过来也一样。你不能出现a里两个不同位置都映射到b里同一个值也不能出现a里同一个值映射到b里两个不同值。具体实现用两个哈希表分别记录a-b和b-a的双向映射。遍历时如果映射已存在且不一致直接返回false否则建立映射。很多人在写单向映射时漏了反向校验导致[1,2]和[2,1]这类对称场景被误判为同构。这个小节看起来和前面的多数元素、最大子数组风格不同但它同样属于“用哈希表做数值关系校验”的范畴是数组题里最容易被快速考到的简单题。我把它放这里是想提醒你数组专题不只考排序查找还大量考映射和状态关系跟着LeetCode热榜刷这类题迟早会碰到。5. 矩阵遍历与回溯顺时针打印和矩阵中的路径5.1 顺时针打印矩阵用边界收缩代替方向判断进入矩阵部分第一道高频题是“顺时针打印矩阵”。题目要求输入一个矩阵按照从外向里顺时针打印每一个元素。这道题几乎每次面试都会有人拿出来因为代码量适中边界条件又极多特别适合考察代码完整性。我的解法思路是“边界收缩”不做复杂的方向切换。维护四个变量top、bottom、left、right每打印完一圈就收缩一圈。每次先从左到右打印top行然后top接着从上到下打印right列然后right--如果top bottom从右到左打印bottom行再bottom--如果left right从下到上打印left列再left。很多人第一次写会漏掉后面两个if判断导致只有一行或只有一列的矩阵打印出多余元素。实际测试时务必加[1,2,3]这种单行矩阵和[[1],[2],[3]]这种单列矩阵它们最能暴露边界条件不完整的问题。这道题还有一个高频变体要求按“之字形”打印矩阵。思路仍然是边界收缩只是在奇数层时把从左到右的打印改成从右到左本质没变但面试时临场推反方向容易晕建议先画一个3×3的矩阵把指针每走一格的位置变化写在纸上再动手写代码。5.2 矩阵中的路径DFS回溯的“状态恢复”细节另一道矩阵高频题是“矩阵中的路径”原题是判断在一个字符矩阵中是否存在一条包含某字符串所有字符的路径路径可以从任意格子出发每一步可以上下左右移动一格不能重复经过格子。这和LeetCode 79单词搜索基本一致。这种题的核心套路是DFS加回溯。从每个格子出发尝试匹配字符串四个方向递归搜索匹配失败就回退。这里最容易出错的地方是“状态恢复”进入一个格子时把这个格子标记为已访问返回前要把标记擦掉否则后续分支无法再次使用这个格子。很多读者问我为什么撤销标记是必须的。举个例子矩阵里有一个“A”和一个“B”你要找“ABA”这条路径。如果第一次从A出发向右走到B再想回到A但这个A已经被标记为已访问不擦除的话就直接返回false了。可实际上路径是可以重复利用起点格子的吗要注意题目要求“不能重复经过格子”但路径往回走的那个格子并不是重复经过而是从B回到起点A起点A在进入B前已经访问过了如果保留标记这个回退就会被禁止。所以撤销标记的本质是让回溯路径上的祖先节点重新变为可用状态。写DFS的时候我推荐的模板是先判断边界和字符匹配再做访问标记递归四个方向最后撤销标记并返回结果。递归终止条件就是当前字符索引等于字符串长度减一。深度优先搜索在LeetCode上通常能用但要注意递归栈的深度如果矩阵特别大可以跟面试官讨论用显式栈迭代版本。5.3 进阶链接用矩阵快速幂优化递推问题矩阵这个方向除了遍历和搜索还有一个面试中经常作为“延伸题”出现的方向矩阵快速幂。热搜词里的“矩阵快速幂”“矩阵·快速幂算法”说的就是这个。剑指Offer里最出名的相关题是“斐波那契数列”——虽然原题用动态规划就能解但面试官进阶一问往往是“能不能用O(log n)算第n项”。这时候把递推关系写成矩阵形式状态向量[F(n), F(n-1)]可以由矩阵[[1,1],[1,0]]乘以前一个状态向量得到求第n项就等价于求这个矩阵的n次幂。矩阵快速幂的思路和整数快速幂完全一致把指数拆成二进制用“幂的平方”累积结果只是底数从整数变成矩阵。写的时候注意矩阵乘法函数别写错循环顺序三重循环里i、j、k的顺序要固定。这道题我在准备面试阶段至少手写了五遍因为矩阵乘法下标一错调试起来非常痛苦。我当时学矩阵快速幂的感受是它看起来像数学玩具其实在状态转移方程的时间复杂度优化上有实际价值。比如有些动态规划题的状态转移是线性的就可以用矩阵加速从O(n)降到O(log n)。这套思路想通了再看“矩阵求逆”“特征值分解”这些线代名词就不会觉得高不可攀算法题里能用到的只是其中很小一部分。6. 数组和矩阵题的工程素养越界、空值、极端输入与测试习惯6.1 最容易翻车的五个位置数组和矩阵题目虽然看起来简单但在笔试环境下翻车率一点都不低。我总结了五个最容易出问题的地方每次刷题前过一遍能少踩很多坑第一个是空数组和null的判断。Joseph很多题默认输入非空但牛客网的测试用例经常给你灌null。最好在函数开头就写统一判空逻辑不要等用到matrix[0]时才报错。第二个是二维数组的matrix[0].length。有些题传进来的是int[0][0]直接取matrix[0]会抛异常判断顺序应该是matrix null、matrix.length 0、matrix[0].length 0一个都不能少。第三个是索引越界。尤其矩阵DFS和旋转数组二分row 1、col - 1这类操作放在边界判断之前还是之后顺序写反了就是一个ArrayIndexOutOfBoundsException。第四个是增量溢出的问题。比如旋转数组里求mid写(left right) / 2如果数组长度接近int最大值leftright会溢出建议统一写left (right - left) / 2。第五个是返回值类型不匹配。原题说“没有这样的数返回什么”一定先看题比如旋转数组最小数字的题目常常默认数组非空返回0或其他占位值就不行。这些看似琐碎的细节在实际笔试里是真真切切能拉开差距的地方。我在公司帮忙筛简历的时候看过不少候选人算法思路完全正确但就是挂在边界case上最后系统判一个用例不过整题零分特别可惜。6.2 一个完整的测试用例清单刷题时我建议你准备一套“通用测试清单”对大部分数组和矩阵题都能用空数组、null输入只有单个元素的数组全部元素相同的数组已经有序或完全逆序的数组目标值在数组两端的情况目标值在数组中但重复多次负数、零、正数混合矩阵只有一行或一列矩阵行数和列数不等长方形矩阵这套清单看着简单但真能覆盖绝大多数边界问题。我在练题阶段每写完一个解法就强制自己跑一遍清单时间久了就会形成肌肉记忆面试时也会先问清楚输入是否保证合法而不是默认一个完美世界。6.3 我个人建议的刷题顺序和节奏最后聊一点比较私人的经验。如果你是刚开始准备算法面试不要直接一头扎进LeetCode随机刷。先按专题过一遍剑指Offer数组和矩阵就是最好的起点因为后面很多链表题、树题最后都会转化为数组的处理逻辑。我说个真实感受树的层序遍历结果是个数组图的邻接矩阵用二维数组存二分查找优化到最后也是在数组上移动指针。数组底子如果打得不牢后面学什么都会觉得飘。我自己的节奏是每天三到四道题先不看题解硬想15分钟想不出来再看思路但看完以后合上答案自己完整写一遍第二天再把这些题复现一遍。这个“第二天重写”的步骤很多人不愿意做但它恰恰是最关键的。因为背出来的解法和真正内化的解法隔一个星期你自己就能分辨出来。如果你已经刷过一遍基础题想进阶可以试试把每道题的多种解法都写一遍并且算清楚各自的时空复杂度。比如二维数组查找既写暴力扫描又写右上角扫描再写每行二分比较它们在不同数据规模下的差异。这个过程比单纯刷题数量更能训练工程判断力——因为真实工作中你选哪套方案不完全取决于“能不能跑”还要看数据量、边界情况、可维护性这些在面试深度追问时最容易被看到。
