准备面试的时候我给自己定过一个原则算法题可以不刷难题但基础题型必须每道都弄得滚瓜烂熟。因为面试官最常出的恰恰不是那些需要奇技淫巧的题而是看一眼数据结构就知道在考什么的“经典题”。数组与矩阵就是这类题的重灾区。这篇博文是我整理剑指Offer数组与矩阵部分的第一篇挑了几道我认为最有代表性、面试出镜率最高的题目把每种解法的思路、代码、复杂度、边界坑一次性讲透。不管你是刚开始刷题还是准备二刷查漏补缺这期内容都能直接拿来用。1. 数组与矩阵类题目的出题逻辑数组这个数据结构太基础了基础到很多人会忽略它在算法面试中的分量。其实数组题的考察重点从来不是“你会不会遍历”而是你对时间复杂度、空间复杂度、边界条件这三件事的敏感度。比如数组元素范围有没有限制、是否允许修改原数组、数据是否有序这些条件只要变一个最优解法可能就完全不同。矩阵本质上是二维数组它多出来的一层考的往往是“定位”和“边界”两个能力。定位是指你怎么利用矩阵行列之间的单调性、对称性来缩小查找范围边界是指你在遍历、打印、交换的过程中如何保证行号和列号不越界、不重复。这两个能力在剑指Offer的二维数组查找和顺时针打印矩阵两道题里体现得最充分。我翻了近几年的面经发现数组与矩阵类的热门题可以按模式分成几类查找类有序查找、二分变形、统计类找重复、找出现次数过半、子段类最大子数组和、遍历类螺旋打印、旋转矩阵。这个分类对我刷题的帮助很大因为同一个模式里的题解题套路是相通的。下面我按这种思路逐个展开讲。2. 二维数组中的查找一招“排除法”打天下2.1 题目与核心思路题目描述很经典一个二维矩阵每一行从左到右递增每一列从上到下递增。给定一个整数 target判断它是否存在于矩阵中。我第一次看到这道题脑子里冒出来的就是两层 for 循环暴力搜复杂度 O(m * n)。这个答案面试官不会满意因为题目里的“行递增、列递增”条件没有被用上。正确的做法是从右上角开始查找。为什么右上角这个位置特殊因为它在行方向上是这一行的最大值在列方向上是这一列的最小值。你可以把它理解成一个“岔路口”如果 target 比它大那 target 一定不在这一行因为这一行所有数都比它小如果 target 比它小那 target 一定不在这一列因为这一列所有数都比它大。每一次比较要么排除一整行要么排除一整列最坏情况下也只需要走 m n 步就能得到结论。2.2 代码实现与复杂度直接给 C 版本这是我平时刷题最常用的语言bool findNumberIn2DArray(vectorvectorint matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int rows matrix.size(); int cols matrix[0].size(); int row 0; int col cols - 1; while (row rows col 0) { if (matrix[row][col] target) { return true; } else if (matrix[row][col] target) { --col; } else { row; } } return false; }时间复杂度 O(m n)空间复杂度 O(1)。从右上角出发最多往左走 n 步、往下走 m 步两条路的步数加起来是 m n不会再多了。我用一个例子走一遍方便你对照理解。假设矩阵是1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15查找 target 7。从右上角的 9 开始9 大于 7排除第 4 列看新的右上角 88 大于 7排除第 3 列再看右上角 22 小于 7排除第 1 行新的右上角是 44 小于 7排除第 2 行现在的右上角恰好是 7返回 true。整个过程只做了 4 次比较比暴力遍历快得多。2.3 为什么从右上角而不是左上角这是个很容易被忽略、但面试官很喜欢追问的点。左上角是矩阵的最小值右下角是矩阵的最大值这两个位置的数字和 target 比较完后你很难判断该往哪个方向走因为比它小的方向不止一个比它大的方向也不止一个。右上角和左下角则不同它们在一个方向上是极值在另一个方向上也是极值天然具备“唯一排除方向”的性质。这道题还有一种对称的写法和右下角从左下角出发相等则返回大于 target 则行号减一小于 target 则列号加一。思路完全一样但写代码时千万不要把两个方向搞混了。我面试的时候亲眼见过一个候选人写着写着就把行和列的方向反了这种错误一出现前面讲得再好也会大打折扣。注意代码里对空矩阵的判断要放在最前面。如果 matrix 为空或者 matrix[0] 为空直接返回 false。尤其是 matrix[0] 为空这种情况不判断的话后面取 matrix[0].size() 会直接越界崩溃。3. 数组中重复的数字三种思路的取舍3.1 题目描述与思路对比题目长度为 n 的数组 nums 里所有数字都在 0 到 n - 1 的范围内。数组中有些数字是重复的请找出任意一个重复的数字。原书里的经典版本有个前提条件就是“所有数字都在 0 到 n - 1 范围内”。这个条件不是白给的它是后面原地交换法的关键。先说结论这道题有三大类主流解法适用场景各有不同。解法时间复杂度空间复杂度是否要求修改原数组前提条件哈希表记录出现次数O(n)O(n)否无排序后遍历O(n log n)O(1)是无原地交换法O(n)O(1)是数字范围必须落在 0 到 n - 1三种方案没有绝对的好坏。哈希表最简单先建一个 unordered_set遍历数组时如果当前数字已经出现在集合里它就是重复数字。这个解法代码最短面试时作为思路铺垫讲出来很好。3.2 原地交换法的原理与实现原地交换法的核心思想是既然数组长度是 n数字范围又恰好是 0 到 n - 1那么每个数字理论上都可以放到“值和下标相同”的位置上。如果下标 i 的位置已经不是数字 i说明这个位置被别的数字占了如果我们在把数字归位的过程中发现目标位置上已经躺着一个和它相同的数字那这个数字就一定重复了。我用大白话给你解释一下想象有 n 个抽屉编号 0 到 n - 1每个球上写着一个数字。正常情况下写着数字 i 的球应该放在编号 i 的抽屉里。现在你逐个把所有球归位当你拿起一个球准备放回它该去的抽屉时发现那个抽屉里已经有一个一模一样的球那不就说明有两个同号的球了吗这就是抽屉原理。代码实现有个细节需要注意交换之后当前下标 i 上可能还不是正确数字所以要用 while 而不是 if 继续处理int findRepeatNumber(vectorint nums) { for (int i 0; i nums.size(); i) { while (nums[i] ! i) { if (nums[nums[i]] nums[i]) { return nums[i]; } swap(nums[i], nums[nums[i]]); } } return -1; }外层 for 循环配合内层 while每一轮交换都会把一个数字放到它的正确位置上而一旦一个数字归位后续就不会再被交换。每个元素最多被交换两次所以即使两层循环嵌套整体均摊复杂度仍然是 O(n)。3.3 面试环节的思路展示建议这道题在面试里很能拉开差距因为它有好几个层面可以聊。你可以在说暴力循环之后主动补充一句“如果允许用 O(n) 的额外空间可以用哈希表时间 O(n)。”然后再抛出关键问题“如果题目要求空间 O(1)就要看能不能修改原数组如果能可以使用原地交换法。”这里有一个非常重要的习惯要养成动手写代码前先确认题目的附加条件。数组里的数字范围是不是 0 到 n - 1允不允许修改原数组需不需要找所有重复数字还是只要一个这三个问题每个都会改变你的解法。我在实际面试中经常看到候选人一上来就开始写哈希完全没有考虑空间限制虽然答案是对的但面试官会觉得你缺乏对复杂度的主动思考。提示如果题目改成“不能修改原数组”原地交换法就失效了。这时有一种二分式的思路通过统计左右两个区间内的数字个数来判断重复数字落在哪边时间复杂度 O(n log n)空间 O(1)。这类变体题在剑指Offer里是单独一道题后面我会展开讲。4. 连续子数组的最大和动态规划的敲门砖4.1 题目与状态定义题目输入一个整型数组数组中的一个或连续多个整数组成一个子数组求所有子数组中和的最大值。要求时间复杂度 O(n)。这道题太经典了经典到几乎所有算法教材里都有。但很多人一开始会卡在状态定义上。想一想如果定义 dp[i] 表示“前 i 个元素的最大子数组和”你会发现递推关系根本写不出来因为最大子数组不一定以第 i 个元素结尾你没法从前一个状态自然推到后一个状态。换一个定义就通了dp[i] 表示以第 i 个元素结尾的连续子数组的最大和。为什么以结尾位置为状态因为连续子数组这个性质决定了递推时当前元素要么接在前一个元素后面要么自己重新开始一段。这两个选择可以用一个转移方程写清楚dp[i] max(dp[i-1] nums[i], nums[i])这个转移方程的含义是以 i 结尾的最大和要么是把 nums[i] 拼接到以 i - 1 结尾的子数组后面代价是承接前面可能为负的结果要么干脆抛弃前面的所有元素让 nums[i] 自己作为新子数组的开头。你选一个更大的就是答案的一部分。4.2 空间优化与代码实现dp[i] 只依赖 dp[i - 1]所以不需要维护整个 dp 数组用一个滚动变量 cur 就够。同时用一个 best 变量记录遍历过程中出现过的最大 dp 值最终答案就是所有可能的“以 i 结尾的最大子数组和”里面的最大值。int maxSubArray(vectorint nums) { int cur 0; int best INT_MIN; for (int x : nums) { cur max(cur x, x); best max(best, cur); } return best; }有一句很重要的经验cur x 和 x 之间的选择本质上是“当前这段连续和如果已经是负数那它对后续的贡献一定小于零不如丢弃重开”。这个判断在面试中不仅是一条解题规则也展示了对动态规划转移逻辑的理解程度。这道题还有一个很常见的追问变体如果子数组允许跨越数组末尾和开头形成循环怎么求最大值思路是把问题拆成两种情况一种是最普通的最大子数组和一种是“整个数组和减去最小子数组和”然后取二者较大值。面试时能聊到这层基本这道题就稳了。5. 旋转数组的最小数字二分查找的变形5.1 题目与二分的关键判断题目把一个有序数组最开始的若干个元素搬到数组末尾称为旋转。输入一个递增排序数组的一个旋转输出旋转数组的最小元素。例如 [3, 4, 5, 1, 2] 是 [1, 2, 3, 4, 5] 的一个旋转最小元素是 1。递增数组整体旋转之后数组会变成两个递增段左段的所有元素都大于等于右段的所有元素最小值恰好是两个段的分界点也就是右段的第一个元素。可以用二分法来找这个分界点。这里的关键判断是二分的时候应该拿 nums[mid] 和谁比很多人的第一反应是和 nums[left] 比这个思路容易掉坑。假设 nums[mid] nums[left]你只能说 mid 很可能在左段但没法确定最小值到底在左段还是右段尤其是旋转了 0 个元素时nums[left] 本来就是最小值。更可靠的做法是拿 nums[mid] 和 nums[right] 比如果 nums[mid] nums[right]说明 mid 落在左段最小值在 mid 右边所以 left mid 1如果 nums[mid] nums[right]说明 mid 落在右段最小值在 mid 位置或者 mid 左边所以 right mid如果 nums[mid] nums[right]无法判断最小值在哪个方向唯一的办法是逐步缩小右边界也就是 right--。int minArray(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; } else if (nums[mid] nums[right]) { right mid; } else { --right; } } return nums[left]; }5.2 退化情况与复杂度分析很多人写二分怕的就是相等的情况。当数组里存在大量重复元素时比如 [1, 1, 1, 0, 1] 或者 [1, 0, 1, 1, 1]单纯靠二分就无法在一次迭代里稳定排除一半区间这就是最坏情况 O(n) 的来源。上面的代码通过 right-- 来处理实际运行中大多数情况下仍然是 O(log n)只有当重复元素特别多的时候才退化成 O(n)。这道题的循环条件是 left right 而不是 left right你可以理解为我们不是要“精确命中”最小值而是不断收缩区间直到区间里只剩一个元素。这种写法的好处是最后返回 nums[left] 时不需要额外判断代码也更好记。我建议你自己跑几个特殊用例验证一下旋转 0 个元素的 [1, 2, 3, 4, 5]、全部相同的 [1, 1, 1, 1, 1]、边界值比如 [3, 1, 3]。把这三个用例在纸上手算一遍二分过程你对这题的把握会比背代码牢靠得多。6. 顺时针打印矩阵边界控制的个体考验6.1 分层打印的思路题目输入一个矩阵按照从外向里以顺时针的顺序依次打印出每一个数字。比如 3 x 4 的矩阵打印顺序是 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。看到这种打印题第一反应应该是“一圈一圈处理”。每一圈的路径都是固定的四条边从左到右打印上边从上到下打印右边从右到左打印下边从下到上打印左边。打印完最外层把四个边界各往里收一格继续打印下一圈。实现时用四个变量控制边界up 表示上边界行号down 表示下边界行号left 表示左边界列号right 表示右边界列号。每次循环打印一圈然后 up 加一、down 减一、left 加一、right 减一直到上下边界或者左右边界交错也就是 up down 或 left right说明所有元素都打印完了。6.2 关键边界条件与代码实现这道题最容易出错的点不是四条边本身而是当矩阵缩小到只剩一行或者只剩一列时四条边的打印会互相重叠。举个例子如果最后只剩一行数据那么先执行“从左到右打印上边”时已经把这一行全部打印完了接着“从右到左打印下边”其实打的是同一行那就会重复打印。所以必须先判断 down up 是否成立成立才执行“从右到左”这一步。同理只剩一列时要判断 right left 再执行“从下到上”。vectorint spiralOrder(vectorvectorint matrix) { if (matrix.empty() || matrix[0].empty()) return {}; vectorint res; int up 0, down matrix.size() - 1; int left 0, right matrix[0].size() - 1; while (up down left right) { // 上边从左到右 for (int j left; j right; j) { res.push_back(matrix[up][j]); } // 右边从上到下 for (int i up 1; i down; i) { res.push_back(matrix[i][right]); } // 下边从右到左前提是还有多行 if (down up) { for (int j right - 1; j left; --j) { res.push_back(matrix[down][j]); } } // 左边从下到上前提是还有多列 if (right left) { for (int i down - 1; i up; --i) { res.push_back(matrix[i][left]); } } up; --down; left; --right; } return res; }你仔细看第三和第四段循环的循环变量很容易犯的一个低级错误是把 matrix[down][j] 写成 matrix[up][j]或者把 matrix[i][left] 的列号写错。这种错误在 IDE 里调试很容易发现但在白板面试里就要靠你手动模拟一两次来避免。注意循环条件 while (up down left right) 和里面的两个 if 判断缺一不可。循环条件负责覆盖“整个矩阵完整排完”的情况两个 if 负责覆盖“最后只剩一行或只剩一列”的退化情况。多想想 1 x N 和 N x 1 这两种极端输入跑一遍代码就明白为什么需要它们了。7. 数组与矩阵题通用的调试与面试技巧7.1 写题之前先确认的四个问题刷了这么多数组题我总结出一个习惯拿到题目后不要急着写代码先把这几个问题在脑子里过一遍或者直接问面试官输入数组是否可能为空空数组的返回值是什么数组元素的范围是否有限制有没有负数、0、极大值是否允许修改原数组对时间复杂度有没有明确要求这四个问题看起来很简单实际上能帮你避开很多坑。比如数组中重复的数字这道题只要问清楚“能否修改原数组”你就能立刻从三四个解法里选出正确的那一个。再比如连续子数组的最大和如果数组长度是 0那么答案是返回 0 还是 INT_MIN也需要提前定义清楚。面试官听到你主动问这些问题往往会在心里给你加分。7.2 数组题的自查清单写完一道题不要立刻说完成先自查这么几项第一循环的初始变量有没有写反尤其是矩阵题里的 row 和 col第二所有数组下标访问是否都落在合法范围内特别注意 nums.size() - 1 可能产生负数下标第三边界情况是否处理完整空数组、单元素数组、全部相同元素都要过一遍第四空间复杂度是否符合题目要求。我举个例子旋转数组最小数字这道题很多人写完二分觉得没问题结果遇到 [1, 3, 3] 这种输入就挂了。原因就是把数组长度 n 当成了循环次数而不是把区间收缩当作循环条件。这类问题只要在提交前手动跑三五个用例基本都能发现。7.3 刷题顺序与后续内容预告数组与矩阵这部分我建议按难度递进刷先做二维数组中的查找这种规律观察题再做调整数组顺序的 double pointer 题然后是数组中重复数字的原地交换法接着是旋转数组的二分变形题最后用顺时针打印矩阵来练习边界控制。这样一轮下来你会发现自己面对大部分数组题时第一反应不再是“暴力遍历”而是主动思考数据规律和复杂度约束。这个系列会持续更新后续我计划按同样的方式整理字符串、链表、二叉树等专题。每个专题我都会保持这个风格题目连着思路讲代码直接可用坑点尽量说透。你可以先收藏这一篇刷题的时候对照着看。在我自己准备面试的那段时间最大的感受是数组题“入门容易精通难”。很多人觉得数组题不就是 for 循环但实际上它最考验一个人的基本功是否扎实。我见过不少候选人算法题结论能说出来但一追到“复杂度为什么是这个”“边界情况怎么处理”就卡壳。所以别急着追求刷题数量每做完一道题多问自己一句如果这个题目的前提条件变一下我的解法还成立吗想清楚这个比无脑刷十道题的价值高得多。