1. 二维数组中的查找：为什么“右上角出发”比暴力扫描更有面试价值
1.1 题目描述与最笨的解法
剑指Offer里数组与矩阵专题的第一道题，通常都是“二维数组中的查找”。我给自家学员讲的时候，喜欢先把原题贴出来：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数。
很多第一次刷题的人第一反应是双重循环暴力扫描，这当然能过，但面试官让你写这道题，图的不是你两分钟写完一个O(n²)的遍历，而是想看你有没有识别出“行列同时递增”这个特殊结构的眼光。我见过不少候选人一上来就写嵌套for，写完还觉得挺稳，结果面试官一句“你能不用两层循环吗”就懵了。
这里要先建立第一个认知：凡是题目里给出“每一行递增、每一列递增”这种约束，一定不是白给的，它在提示你数据具有某种局部有序性，可以做到比全量扫描更快的查找。暴力解不是不能用，而是它浪费了题目给的核心条件，相当于把一张藏宝图当成白纸擦桌子。
1.2 右上角坐标的意义：同时淘汰一行和一列
解法是选右上角（或者左下角）作为起点，这不算什么新鲜结论，但很多人只知道“用右上角”，并不知道为什么是右上角。我换个方式解释：右上角的元素拥有双重身份——它是它所在行的最大值，同时是它所在列的最小值。
这个双重身份带来的好处是：拿目标值和它比较一次，无论结果是大于还是小于，你都能确定性地淘汰一整行或一整列。具体来说，从右上角开始，如果目标值小于当前元素，那目标值不可能出现在当前这一列，因为这一列从上到下是递增的，右上角已经是这列最小的了，所以整列可以直接丢弃，指针左移；如果目标值大于当前元素，那目标值不可能出现在当前这一行，因为当前元素是这行最大的，所以整行丢弃，指针下移。每比较一次，搜索范围就缩小一行或一列，最坏情况下从右上角走到左下角，步数等于行数加列数，时间复杂度O(m+n)。
这种“一次比较淘汰一大片”的思路，比二分更灵活。二分要求数据在一维上有严格单调性，而这里矩阵只在行和列两个方向上分别单调，单独拿哪一行出来二分也能做，但那样每一行都二分一次就是O(m·log n)了，不如O(m+n)的右上角扫描。更关键的是，这种“利用角点特性同时压缩两个维度”的思想，在后面的矩阵题里会反复出现。
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指向6，nums[mid] > nums[high]，说明断点在mid的右侧，也就是最小值在右半边，所以low移到mid+1。反之若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最大值，left+right会溢出，建议统一写left + (right - left) / 2。
第五个是返回值类型不匹配。原题说“没有这样的数返回什么”一定先看题，比如旋转数组最小数字的题目常常默认数组非空，返回0或其他占位值就不行。
这些看似琐碎的细节，在实际笔试里是真真切切能拉开差距的地方。我在公司帮忙筛简历的时候看过不少候选人，算法思路完全正确，但就是挂在边界case上，最后系统判一个用例不过，整题零分，特别可惜。
6.2 一个完整的测试用例清单
刷题时我建议你准备一套“通用测试清单”，对大部分数组和矩阵题都能用：
- 空数组、null输入
- 只有单个元素的数组
- 全部元素相同的数组
- 已经有序或完全逆序的数组
- 目标值在数组两端的情况
- 目标值在数组中但重复多次
- 负数、零、正数混合
- 矩阵只有一行或一列
- 矩阵行数和列数不等（长方形矩阵）
这套清单看着简单，但真能覆盖绝大多数边界问题。我在练题阶段每写完一个解法，就强制自己跑一遍清单，时间久了就会形成肌肉记忆，面试时也会先问清楚输入是否保证合法，而不是默认一个完美世界。
6.3 我个人建议的刷题顺序和节奏
最后聊一点比较私人的经验。如果你是刚开始准备算法面试，不要直接一头扎进LeetCode随机刷。先按专题过一遍剑指Offer，数组和矩阵就是最好的起点，因为后面很多链表题、树题，最后都会转化为数组的处理逻辑。我说个真实感受：树的层序遍历结果是个数组，图的邻接矩阵用二维数组存，二分查找优化到最后也是在数组上移动指针。数组底子如果打得不牢，后面学什么都会觉得飘。
我自己的节奏是每天三到四道题，先不看题解，硬想15分钟；想不出来再看思路，但看完以后合上答案自己完整写一遍；第二天再把这些题复现一遍。这个“第二天重写”的步骤很多人不愿意做，但它恰恰是最关键的。因为背出来的解法和真正内化的解法，隔一个星期你自己就能分辨出来。
如果你已经刷过一遍基础题，想进阶，可以试试把每道题的多种解法都写一遍，并且算清楚各自的时空复杂度。比如二维数组查找，既写暴力扫描，又写右上角扫描，再写每行二分，比较它们在不同数据规模下的差异。这个过程比单纯刷题数量更能训练工程判断力——因为真实工作中，你选哪套方案不完全取决于“能不能跑”，还要看数据量、边界情况、可维护性，这些在面试深度追问时最容易被看到。
` 自动生成 JNI 头文件)
