Hot 100里的普通数组与矩阵专题看起来是整个清单里最朴素的板块实际上却是面试出场率最高的一批题。我见过太多次这样的场景面试官先用一道“轮转数组”或“矩阵置零”热场然后顺着你的实现一路追问复杂度与边界条件。如果你只背过答案而没想清楚背后的算法思维往往会在追问环节露馅。这篇内容不是单纯列题解而是把这九道题串成一张“能力图谱”讲清楚每道题在练什么、用什么套路、面试怎么讲以及我反复提交过程中踩过的坑。无论你是刚开始刷题的新人还是准备冲刺面试的老手普通数组与矩阵专题都值得单独花时间梳理。它不考复杂的贪心或深奥的图论却集中考察几类最底层的算法能力动态规划的状态定义、排序后的贪心、原地修改的空间设计、边界收缩的循环不变量。这些能力是所有后续难题的“地基”地基不牢遇到真正高难度的题目就会露怯。1. 这个专题到底在考什么普通数组与矩阵的能力图谱先说一个很多人忽略的事实Hot 100里这两类题加在一起有九道左右数量并不多但每一道都对应一种独立的算法思想几乎没有重复考察同一个套路的题。这和我最初预想的“简单题合集”完全相反。数组和矩阵本身是最基础的数据结构正因为基础才能在一道题里干净利落地考察某个单一算法点不掺杂其他干扰。普通数组里的五道题分别对应五种不同的能力题目核心考察点最常用解法最大子数组和动态规划状态定义一趟扫描维护“以当前元素结尾”的最大和合并区间排序 贪心按起点排序逐段合并轮转数组原地操作的数学规律三次翻转除自身以外数组的乘积前缀积 / 后缀积两次遍历填答案数组缺失的第一个正数原地哈希空间极限利用把每个数放到它“该在”的位置上矩阵四道题则更聚焦两个方向一个是“如何用常数额外空间完成标记”典型代表是矩阵置零另一个是“如何用循环不变量描述二维遍历”典型代表是螺旋矩阵、旋转图像。搜索二维矩阵 II 则把二维问题降维成一维考察的是观察能力。把这九道题放在一起看能提炼出两个共同的底层逻辑。第一绝大多数数组题暴力解都很容易想到真正的门槛在于“优化空间或优化时间”时的临时状态设计。比如最大子数组和暴力枚举所有子数组是 O(n^2)但你一旦把“以 i 结尾”作为状态整个问题就变成了 O(1) 额外空间的一趟扫描。这就是状态定义的价值。第二矩阵题的核心挑战永远是“坐标变换不要乱”。不管是螺旋矩阵的边界收缩还是旋转图像的转置本质上都是在维护一套一致的坐标变换规则。很多人在白板上能写对整体逻辑但一到边界就乱套归根结底是没有把“循环不变量”定义清楚。我在刷完这一批题之后最大的感受是它们几乎不需要背诵你只需要想清楚“我究竟在维护一个什么状态”其他一切都顺理成章。2. 普通数组五连从最大子数组和到缺失正数这一节我把五道题逐个拆开重点不是贴完代码就完事而是讲清楚每道题方案的由来——为什么这么做是对的以及换一个条件它为什么就不成立。搞清楚了这些面试追问环节你才能不慌。2.1 最大子数组和一道题吃透动态规划的“以谁结尾”思维最大子数组和是动态规划入门的经典题但它真正的考点不是递推公式本身而是“为什么状态只能定义为以 i 结尾的最大和而不是前 i 个元素的最大和”。你可以试一下如果定义 dp[i] 为“前 i 个元素里某个子数组的最大和”那么你根本没法递推因为你不知道这个最大和的子数组从哪里开始也无法判断要不要把 nums[i] 接上去。但你一旦定义 dp[i] 为“以 nums[i] 结尾的最大子数组和”递推关系就非常自然要么自己单独成为子数组要么接上 dp[i-1]。nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] # dp[i] max(nums[i], dp[i-1] nums[i]) # 空间优化只用两个变量即可 cur 0 best nums[0] for x in nums: cur max(x, cur x) best max(best, cur) print(best) # 6对应子数组 [4, -1, 2, 1]一个特别容易踩的坑是 best 的初始值。如果你把它设成 0而数组全是负数最终答案会错误地变成 0。所以要么初始化为第一个元素要么用负无穷。我第一次提交就是在全负数组上挂掉的这个问题在面试现场也很容易在边界测试里暴露。平时练习时可以顺便想一想它的变体如果数组是环形的允许首尾相连该怎么办思路是把问题拆成“普通最大子数组和”和“数组总和减去最小子数组和”两种情况取最大值。这就是面试里常见的“追问拓展”方向。2.2 合并区间排序之后的贪心为什么永远有效合并区间这题几乎所有人第一反应都是“先排序再遍历合并”。但面试官更想听的是你解释清楚为什么排序之后贪心就一定正确。关键点在于重叠关系。我们把所有区间按左端点升序排列后任意两个区间如果左端点小的在前那么只有当后一个区间的左端点不超过前一个区间的右端点时它们才可能重叠。此时合并区间只需要把右端点更新为两者中的较大值然后继续和下一个比较。因为排序已经保证了左端点的有序性所以贪心合并时“左边已经处理过的区间不会和更后面的区间发生意外的重叠漏判”。def merge(intervals): intervals.sort(keylambda x: x[0]) res [] for start, end in intervals: if not res or start res[-1][1]: res.append([start, end]) else: res[-1][1] max(res[-1][1], end) return res我实际写代码时的一个经验先在纸上画几条不同位置关系的线段比如完全不相交、包含、交叉、紧挨着但没完全重叠然后再动手写逻辑准确率会明显提高。这题有个常用变体是“插入区间”要求在一个已经合并好的区间列表里插入一个新区间再合并。如果你理解了“排序后贪心”的本质插入区间的解法其实就是在有序数组上做一次二分定位再合并复杂度可以压到 O(n)。还有一个容易被追问的细节区间本身已经按左端点排序了还需要重新排序吗答案是仍然需要因为输入数据可能并未保证有序。面试时主动说出“我先假设输入是无序的所以排序是必要步骤”会显得思路完整。2.3 轮转数组三次翻转的数学直觉轮转数组这题最容易想到的解法是开辟一个新数组把每个元素放到 (i k) % n 的位置时间复杂度 O(n)空间复杂度 O(n)。但题目如果要求原地完成三次翻转就是最优解。三次翻转为什么成立你可以从元素位置移动的角度来看。整体翻转一次后每个元素的位置相对整个数组发生了镜像变化。前 k 个元素被翻转到数组尾部后 n-k 个元素被翻转到数组头部。此时再分别对这两段做翻转就把整段元素从“镜像后再镜像”变回了正确的相对顺序。def rotate(nums, k): n len(nums) k % n # 关键k 可能大于 n nums.reverse() nums[0:k] reversed(nums[0:k]) nums[k:n] reversed(nums[k:n])这里 k % n 这一步极端重要。k 可能比 n 大很多直接翻转时如果忘记取模结果会出错。我见过不止一个人在面试中写完整段逻辑唯独漏了这一行最后被面试官抓住。还有一个容易弄混的细节三次翻转的顺序有三种等价写法。比如可以先翻转前 n-k 个再翻转后 k 个最后整体翻转。哪种写起来不容易错就见仁见智了。我的习惯是“整体翻转、前 k 个、后 n-k 个”因为和 k 直接相关的那段放在最前面思考起来更直观。2.4 除自身以外数组的乘积前缀和后缀的双向扫描这道题有一个明显的“陷阱”如果你直接想到用所有数的乘积除以每个元素那么当数组中有 0 时这个方案立刻失效。所以正确思路是避开除法用“前缀积 × 后缀积”的组合来构造答案。基础做法是用两个数组pre[i] 表示 nums[0] 到 nums[i-1] 的乘积suf[i] 表示 nums[i1] 到 nums[n-1] 的乘积然后 answer[i] pre[i] * suf[i]。但面试的加分项是把额外空间从 O(n) 压到 O(1)也就是只用一个答案数组再在反向遍历时用一个变量滚动记录后缀积。def productExceptSelf(nums): n len(nums) ans [1] * n left 1 for i in range(n): ans[i] left left * nums[i] right 1 for i in range(n - 1, -1, -1): ans[i] * right right * nums[i] return ans第一次正向遍历时ans[i] 存的是 i 左边所有元素的积第二次反向遍历时乘上右边所有元素的积得到的就是除自身外的乘积。这个写法的巧妙之处在于它完全没有用到除法所以不会掉进 0 的坑里。我刷题时习惯把一个特殊场景记在笔记里如果数组里有两个 0那么所有答案都应该是 0。如果你选择了“先算乘积再除”的方案这个场景会让你彻底翻车。用前缀后缀法的话这个结论会从代码逻辑中自然体现完全不需要单独处理。2.5 缺失的第一个正数原地哈希空间极限的经典设计缺失的第一个正数是这批数组题里我公认最难的一道也是区分“背过答案”和“真懂原理”的分水岭。题目限定时间复杂度 O(n)、额外空间 O(1)这个限制基本堵死了排序和哈希表的常规路。真正正确的做法是“原地哈希”既然要找的是缺失的最小正整数那答案一定落在 1 到 n1 这个范围内n 是数组长度。所以我们可以让数组下标和值形成一对一的对应关系把 1 放到下标 0把 2 放到下标 1……遍历结束后第一个“下标 i 上的值不是 i1”的位置就是缺失的那个数。def firstMissingPositive(nums): n len(nums) for i in range(n): while 1 nums[i] n and nums[nums[i] - 1] ! nums[i]: idx nums[i] - 1 nums[i], nums[idx] nums[idx], nums[i] for i in range(n): if nums[i] ! i 1: return i 1 return n 1这里采用 while 而不是 if是因为交换过来的新值可能仍然在 1 到 n 范围内且不在正确位置需要继续处理直到当前位置变成正确值或遇到无效值为止。写代码的时候要注意交换顺序先用 idx 保存目标位置再交换否则先修改 nums[i] 会导致目标下标计算错误。这个思路本质上是用数组本身充当哈希表我每次想到它都会感慨空间复杂度的极致利用。如果面试时你能把“为什么答案一定不超过 n1”作为开场白讲出来整个答题节奏就稳了。3. 矩阵四题循环不变量与降维打击矩阵题的共性比数组题更明显它们基本都在考察“坐标变换的控制力”。代码本身不长真正的敌人是边界混乱和空间复杂度过高。3.1 矩阵置零把标记藏在边界空间从 O(mn) 降到 O(1)最直观的做法是开两个数组分别记录哪些行、哪些列需要置零额外空间是 O(mn)。这道题的进阶要求是原地完成也就是额外空间只有 O(1)。关键洞察是第一行和第一列本身就可以充当标记数组。我们遍历整个矩阵时如果发现某个位置 matrix[i][j] 是 0不需要立刻修改它而是把“i 行需要置零”的信息记录在 matrix[i][0]“j 列需要置零”的信息记录在 matrix[0][j]。但这里有个经典的坑第一行和第一列本身也可能一开始就有 0如果你直接用它们做标记原始信息就被覆盖了。所以必须先单独记录第一行和第一列是否原本包含 0最后再补处理。def setZeroes(matrix): m, n len(matrix), len(matrix[0]) first_row_has_zero any(x 0 for x in matrix[0]) first_col_has_zero any(matrix[i][0] 0 for i in range(m)) for i in range(1, m): for j in range(1, n): if matrix[i][j] 0: matrix[i][0] 0 matrix[0][j] 0 for i in range(1, m): for j in range(1, n): if matrix[i][0] 0 or matrix[0][j] 0: matrix[i][j] 0 if first_row_has_zero: for j in range(n): matrix[0][j] 0 if first_col_has_zero: for i in range(m): matrix[i][0] 0这个方案我最开始看的时候只觉得精妙后来亲手写一遍才发现还有很多细节值得体悟第一遍标记时要从下标 1 开始不能把第一行第一列自己标记成 0 的信息和原有信息搞混。第二遍置零时同样要从 1 开始最后再单独处理边界。这个顺序不能乱否则很容易把正确的标记覆盖掉。3.2 螺旋矩阵四条边收缩时循环不变量怎么定螺旋矩阵要求按顺时针螺旋顺序输出矩阵所有元素。这个题没有算法难度纯粹考验你能否维护好四个边界top、bottom、left、right。我见得最多的错误写法是每走完一条边就盲目执行下一条边的循环导致在只有一行或只有一列时下边的循环和左边的循环会重复读取已经访问过的元素。正确的做法是在每一轮循环里走完上边和右边后用 if 语句检查 top bottom、left right 是否仍然成立再决定是否走下边和左边。def spiralOrder(matrix): res [] if not matrix: return res m, n len(matrix), len(matrix[0]) top, bottom, left, right 0, m - 1, 0, n - 1 while top bottom and left right: for j in range(left, right 1): res.append(matrix[top][j]) top 1 for i in range(top, bottom 1): res.append(matrix[i][right]) right - 1 if top bottom: for j in range(right, left - 1, -1): res.append(matrix[bottom][j]) bottom - 1 if left right: for i in range(bottom, top - 1, -1): res.append(matrix[i][left]) left 1 return res这里循环不变量是“每一轮循环遍历一圈完整的螺旋圈”并且每走完一条边就收缩对应的边界。写完代码之后建议用一个 1×3 的矩阵和 3×1 的矩阵做测试这两个特殊形状最容易暴露重复访问的 bug。我还试过另一种写法用 move 数组进行方向切换碰到边界或已访问元素就转向。这种模拟写法的优点是逻辑简单缺点是需要额外开一个 visited 数组空间复杂度会变成 O(mn)。如果题目没有特别要求空间模拟法也是可以接受的但既然能零额外空间做出来我建议优先掌握边界收缩法。3.3 旋转图像转置加翻转为什么是对角线旋转图像要求把 n×n 矩阵顺时针旋转 90 度而且必须原地操作。两种主流解法里我认为“先转置再水平翻转”最不容易出错因为它把二维变换拆成了两步大家都熟悉的一维操作。为什么是转置加水平翻转而不是转置加垂直翻转你可以拿一个 2×2 的矩阵手推一遍。顺时针旋转 90 度等价于沿着主对角线做镜像转置再沿垂直中线做镜像水平翻转。反方向的话逆时针 90 度就是先转置再垂直翻转。def rotate(matrix): n len(matrix) for i in range(n): for j in range(i 1, n): matrix[i][j], matrix[j][i] matrix[j][i], matrix[i][j] for i in range(n): for j in range(n // 2): matrix[i][j], matrix[i][n - 1 - j] matrix[i][n - 1 - j], matrix[i][j]另一个原地方案是按“环”处理每个环上做四元素轮换。这个写法更省常数时间但坐标容易搞乱。我的经验是面试中时间紧张选择不容易写错的方法更重要。你可以先说出“有转置加翻转和四元素轮换两种方案我先用转置法更直观”然后顺手写出来再补充说明另一种方法的存在— 效果非常好。3.4 搜索二维矩阵 II从右上角出发把二维问题降成一维搜索二维矩阵 II 的矩阵每行从左到右递增每列从上到下递增要求高效查找目标值。你如果试图对每一行二分复杂度是 O(m log n)虽然是可行的但没抓住这道题最有价值的观察。最有名的解法被称为“靠右上角逐步逼近”从右上角开始当前值大于 target 就向左移动一列小于 target 就向下移动一行。这么做之所以可行是因为右上角的元素是它所在行的最大值、所在列的最小值就像一个“决策边界”。向左移动可以排除一整列向下移动可以排除一整行。def searchMatrix(matrix, target): m, n len(matrix), len(matrix[0]) r, c 0, n - 1 while r m and c 0: if matrix[r][c] target: return True if matrix[r][c] target: c - 1 else: r 1 return False我之前一直以为这个矩阵题可以直接用二分后来在面试模拟中发现直接二分因为复杂度不是最优容易被认为没有抓住题目的特殊结构。从右上角出发的做法时间复杂度只有 O(mn)而且代码极其短在面试中写出来会让面试官明显感受到“你理解了这个矩阵的排序含义”。如果面试官追问“为什么从左上角不行”答案是左上角是全局最小值向右向下都比它大没法做任何排除决策。这类题拿到手之后第一件事永远是观察数据的特殊性质而不是立刻套用通用算法。4. 两周刷题计划从零到专题内化很多读者问过我这九道题到底该怎么安排练习节奏。我给的建议很简单不要平均发力按“难度螺旋上升”的顺序两周内完成第一轮完整刷写。第一周算法思维建立期。每天刷一至两道顺序建议是最大子数组和、合并区间、除自身以外数组的乘积、轮转数组、搜索二维矩阵 II。这五道题相对友好能让你先建立“状态定义”“排序贪心”“前缀积”“原地翻转”“降维观察”这五种基础思维的直觉。每道题写完不算完要把官方题解里比你更好的实现也手抄一遍并对比自己写的版本差在哪里。第二周复现与变体扩展期。剩下的四道题缺失的第一个正数、矩阵置零、螺旋矩阵、旋转图像放在这个阶段因为它们更考验边界控制和空间优化。前三天每天一道硬骨头后两天把九道题全部重新盲写一遍。这里的盲写是指不看任何提示直接写出核心代码并跑通测试用例。以下是我自己实测比较舒服的时间分配表格天数任务目标第 1 天最大子数组和 合并区间掌握状态定义和排序贪心第 2 天除自身以外数组的乘积理解前缀积双向扫描第 3 天轮转数组 搜索二维矩阵 II掌握原地翻转和降维观察第 4 天复习前五题限时 20 分钟/题第 5 天矩阵置零 螺旋矩阵吃透标记复用和循环不变量第 6 天旋转图像 缺失的第一个正数突破坐标变换和原地哈希第 7 天全部九道题盲写检验真实掌握程度这个计划里最容易被忽略的是“限时”。在完全没有时间压力的情况下人的大脑很容易陷入“慢慢调代码直到通过”的状态这在真实面试中是致命的。所以第二周开始我强烈要求自己每道题从读题到跑通不超过 25 分钟。如果超时说明没吃透标记下来第二天重刷。刷完之后我还建议做一次“同类扩展”把最大子数组和改成环形数组和把合并区间改成插入区间把螺旋矩阵改成逆时针遍历。这些变体题常作为追问出现提前练习过面试时的反应速度和信心都会完全不一样。5. 面试现场这些题出现在白板上时怎么讲刷题和面试是两回事。代码写得对不代表你能在短时间内让面试官相信你写得对。这里总结我自己的实战表达结构直接套用即可。第一步复述题意并确认条件。比如轮转数组需要先确认是否能使用额外空间、k 是否可能大于 n比如矩阵置零需要确认空间复杂度要求。这个步骤很多人跳过但它是展示你专业性的好机会。第二步先说暴力方案再说优化方案。哪怕你脑子里已经知道最优解也建议先花一分钟陈述暴力解的时间复杂度再引出优化方案。这不是废话而是向面试官展示你有“从朴素到优化”的思考习惯。比如除自身以外数组的乘积先提“总乘积除以自身”被 0 破坏因此要避开的理由再提前缀后缀法。第三步写代码前先描述状态或循环不变量。我通常在写任何代码之前用一两句话告诉面试官“我准备维护一个什么状态”。比如最大子数组和我会说“维护以当前元素结尾的最大子数组和每次取当前元素和累加和的较大值”。这句话一出口面试官就知道你没在背答案。第四步写代码时边写边做小的解释但不要每行都解释。注释关键步骤比如轮转数组的 k % n或者矩阵置零里最后单独恢复第一行第一列。这些地方大概率是面试官想考察的边界点主动说出来比等他问要好。第五步跑一个小的测试用例。白板代码不需要真跑程序但你可以手动模拟一个 3×3 矩阵或一个长度为 5 的数组带大家走一遍代码的核心逻辑。这个动作非常加分因为它证明了你的代码是“真正可以运行的逻辑”而不是默写出来的行尸走肉。这五步说完之后面试官通常只剩一两个追问点要么是空间复杂度的进一步优化要么是某个边界场景的处理。只要你对每道题的原理理解到位这一关基本稳过。6. 提交记录里的避坑清单这九道题我前前后后提交了很多次把踩过的坑整理成了一份自己的清单。写在这里希望能帮你少交几次学费。数组越界轮转数组忘记对 k 取模导致整体翻转后分段翻转的下标超出数组范围。任何写数组翻转的地方都要先想一下 k 与 n 的关系。缺失的第一个正数中交换数组元素的下标由 nums[i] - 1 得到必须先确保 nums[i] 在 [1, n] 范围内才能做这个下标运算。初始值错误最大子数组和的 best 初始值设为 0导致全负数数组返回错误结果。统一初始化为数组第一个元素或负无穷。合并区间的 res 为空时不能直接比较 res[-1]要先判断 res 是否为空。边界污染矩阵置零如果先处理第一行和第一列的原始状态再用它们做标记原始信息会丢失。正确顺序是先记录、再标记、再补处理边界。旋转图像转置时内层循环要从 i 1 开始如果从 0 开始等于把同一个元素交换两次矩阵根本不会发生变化。重复访问螺旋矩阵在单行或单列情况下不加 if 判断直接走下边和左边会把已经输出的元素再走一遍。代码里 top bottom、left right 这两个检查不能省。贪心前提遗漏合并区间如果跳过排序直接合并结果不可能正确。就算题目给的示例恰好是有序的也要在代码里先 sort。这份清单里的大部分错误我都犯过不止一次后来形成习惯每写完一道题先主动检查上述几类问题再提交。这样不仅能提升通过率还能在面试时主动避坑比返工调试更有底气。如果把这九道题当作一个整体来看它们其实共同指向一个核心能力面对一个基础数据结构你能不能找到一条从暴力到最优的升级路径并把它清楚地表达出来。数组和矩阵是最容易出这类考察的数据结构所以它出现在面试开场的频率才会那么高。把这一批题吃透你收获的不仅是九道题的解法更是一整套处理数据结构基础问题的思维方式。