准备面试的时候大家几乎都绕不开“剑指Offer算法题一数组与矩阵”这一组题目。原因很简单数组是绝大多数数据结构的底层形态字符串、堆、哈希表底层都离不开它而矩阵又是二维数组最常见的业务形态。一个候选人能不能把数组题写稳、把边界想清、把复杂度说透基本能直接看出代码功底和工程素养。这篇文章我从面试官视角也从一个刷过大量题目的开发者视角把数组与矩阵这一大类的解题套路、经典题目和踩坑记录完整拆一遍。1. 从面试场景看数组与矩阵类题目1.1 为什么这类题永远是高频考点绝大多数面试官喜欢数组与矩阵题不是因为它难而是因为它“可深可浅”。浅的版本候选人只要能写双层循环遍历就能过深的版本需要你做剪枝、做二分、做原地交换、做回溯每层都能拉开差距。更重要的是数组题的代码量通常不大面试官可以在有限的四十五分钟里完整看到候选人的思考链路如何理解题目、如何选数据结构、如何处理边界、如何自测用例。这比扔一个大型系统设计题更高效。所以“剑指Offer算法题一数组与矩阵”几乎是所有题库的第一道门槛也是我建议每个候选人优先吃透的部分。还有一个容易忽略的原因数组题目里藏着大量“思维惯性陷阱”。比如看到二维矩阵就以为只能暴力O(n^2)看到排序数组就想传统二分看到需要多次查询就无脑哈希表。这些惯性恰恰是面试官想考察的点。能把惯性打破、找到更优解远比会背代码重要。1.2 这类题目到底在考什么我不太赞成把刷题单纯理解为“背题型”。数组与矩阵题背后是四个核心能力第一建模能力。把业务问题抽象成数组的索引、位置、区间关系。比如“旋转数组的最小数字”本质是“被切了一刀的两段递增序列”“矩阵中的路径”本质是二维平面上的深度优先搜索。第二边界控制能力。数组题90%的Bug都出在数组越界、空数组、单元素数组、相邻索引判断上。候选人能不能写出不依赖IDE提示就能手跑通过的代码是面试官非常看重的点。第三时间与空间权衡能力。很多题存在“暴力解、常规解、最优解”三层解法。例如找数组中重复的数字哈希是O(n)空间原地交换可以压到O(1)空间这种优化不是炫技是真实生产中控制内存的习惯。第四代码可读性。面试代码不是竞赛代码面试官需要读懂。变量命名、函数抽离、边界注释这些习惯比“AC更快”更打动人。1.3 题目地图从高频到冷门根据当年刷题和后来模拟面试的经验数组与矩阵相关题目大致可以分成三个梯队高频题二维数组中的查找、旋转数组的最小数字、调整数组顺序使奇数位于偶数前面、顺时针打印矩阵、数组中的重复数字、矩阵中的路径、机器人的运动范围。中频题数组中出现次数超过一半的数字、连续子数组的最大和、和为S的两个数字、和为S的连续正数序列、数组中的逆序对、构建乘积数组、扑克牌顺子。低频但值得做的题数字在排序数组中出现的次数、只出现一次的数字、滑动窗口的最大值。这些题目数量看起来不少但把它们按解题思路归纳后会发现真正需要熟练掌握的“套路”只有五类。我把这五类放在下一节详细拆开这也是整个数组与矩阵篇章的精髓。2. 五个核心套路先建立解题直觉2.1 双指针把O(n^2)降到O(n)的利器一提到双指针很多人第一反应是“快慢指针查链表环”但在数组题里双指针的用途要广得多。我习惯把双指针分成两类对撞指针和快慢同向指针。对撞指针的经典场景是一个指针在数组头部一个在尾部通过某种规则向中间收缩。典型例子是“和为S的两个数字”。给定递增数组和目标值暴力解法是双重循环O(n^2)。但用左右指针相加太大就让右指针左移相加太小就让左指针右移一次遍历就能解决O(n)。这个套路的关键是数组有序因为只有单调性才能保证“指针移动方向是确定的”。快慢指针的经典场景是一个指针遍历整个数组另一个指针指向目标位置。比如后面要讲的“调整数组顺序使奇数位于偶数前面”慢指针始终指向下一个奇数应该放的位置快指针负责探测奇数。这个写法可以保持元素相对顺序相当于一种稳定的原地划分。你可以在白板上先画一个长度五六的示例数组手动走一遍指针移动再写代码命中率会高很多。我最常提醒候选人的一句是双指针的每一轮移动必须保证这个移动不会跳过潜在答案否则就会漏解。2.2 二分查找的变种不只是有序数组如果说双指针是数组题的入门钥匙二分查找就是进阶分水岭。传统二分的条件是“有序数组找某个值”但剑指Offer里的考察远比这个复杂。常见变种有三种。第一种是边界查找。要在一个有序数组里找某个数第一次出现的位置或最后一次出现的位置。核心变化是找到目标后不急着返回而是继续压缩区间直到逼近边界。第二种是旋转数组。数组原本递增从某个位置旋转后形成两段递增区间。比如[3,4,5,1,2]。传统二分里我们比较mid和target这里比较的则是mid与right。为什么看right而不是left因为旋转点后面的那一段一定满足“每个元素都不大于前一段的末尾”而right恰好是后段的最大值。通过比较nums[mid]和nums[right]可以判断mid落在左段还是右段从而确定最小值在哪一侧。第三种是二维查找和峰值查找。二维数组的行列递增查找利用的是“右上角或左下角的特殊位置”每次比较都可以排除一行或一列本质上也是一种二分思想的变体。用生活类比来解释这些二分变种二分不只是“查字典翻页码”更像是“根据一个单调性质不断缩小嫌疑范围”。你并不一定在找一个精确值而是在找“性质变化的分界点”。一旦建立这个认知很多题目会豁然开朗。2.3 哈希与“空间换时间”简单有效的常规武器碰到数组题最自然的思路就是“查表”。比如判断数组里有没有重复数字、统计某个数字出现次数、找到出现次数超过一半的数字哈希表几乎都是秒杀工具。它让查询复杂度从O(n)变成O(1)整体从O(n^2)变O(n)代价是额外空间O(n)。在实际面试里我通常会先给哈希方案再问一句“如果允许修改原数组能不能做到O(1)额外空间” 这就是剑指Offer里非常经典的“原地置换”思路把数字放到它应该出现的下标位置上如果有两个数字想占同一个位置那就是重复。比如数组长度为n元素范围在0到n-1扫描时如果nums[i]不等于i就去和nums[nums[i]]交换如果对方已经等于nums[i]说明重复。整个过程每个元素最多被交换几次整体还是O(n)但空间O(1)。这告诉选手一件事空间换时间不是唯一出路数组本身被修改的能力往往是最强解法。2.4 原地铁律搞清楚题目允不允许改动接上面一点数组题有一个非常实用的“面试暂停点”动手写代码前先确认“给定的数组可以修改吗”。这不是废话它直接决定了可用方案。很多我模拟面试过的候选人在“数组中重复的数字”这道题上一上来就用哈希明明题目允许原地交换却因为没问清楚而错过更优解。而另一些候选人明明题目说清楚“不能修改原数组”依然写出了原地排序的解法这就是读题不细。我的建议是把“能否修改原数组”作为数组题的第一步判断条件进入下面的分支可以修改优先想原地交换、排序、partition思想。不可以修改优先想哈希、前缀和、二分查找。真实业务里接口输入的数组往往是别人复用的对象你原地排序可能破坏调用方状态这也是为什么面试官在意这个细节。2.5 回溯法矩阵是天然的搜索棋盘矩阵类题目和纯数组题目最大的不同是它自带“空间关系”上下左右四个方向。搜索路径、判断可达、统计连通区域都逃不开图的遍历。剑指Offer里“矩阵中的路径”和“机器人的运动范围”就是这一类的代表。很多人觉得回溯难其实核心就四个字尝试、回退。从一个格子出发朝四个方向探索如果当前方向走不通就回到上一格子换一个方向。为了防止一个格子被重复走需要一个visited标记数组进入时置True回退时置False。这里的常见错误有两个一是忘记回退时重置visited导致一条路径失败后其他路径也不能再使用这个格子二是没有先判断行列越界就访问数组直接抛异常。每次在递归开头做越界检查是矩阵回溯的默认写法我会在后面的代码里完整演示。从考察点来看回溯题考的不是你对算法有多熟而是递归状态管理能力。能在五分钟内把“进入、标记、探索、回退、撤销标记”这个五步流程写清楚的人工程里处理业务递归任务也会更有章法。3. 经典题完整拆解与代码实现3.1 二维数组中的查找题目描述很直接给定一个二维矩阵每一行从左到右递增每一列从上到下递增输入一个整数判断矩阵里是否存在。暴力解法是遍历所有格子时间O(rows*cols)。但利用数据规律可以把查找起点选在右上角这个位置的值是它所在行最大的、所在列最小的。如果目标值比右上角小说明当前列下方所有值都更大可以排除掉这一整列指针左移。如果目标值比右上角大说明当前行左边所有值都更小可以排除这一整行指针下移。每次比较要么排除一行要么排除一列总共最多走rowscols步时间复杂度O(rowscols)。def find_in_matrix(matrix, rows, cols, target): if not matrix or rows 0 or cols 0: return False row, col 0, cols - 1 while row rows and col 0: current matrix[row][col] if current target: return True if current target: col - 1 else: row 1 return False这里最容易踩的坑是把左下角当起点也能做但很多人写出来的条件会乱。我的建议是固定采用“右上角if大于列左移else行下移”逻辑最简单不容易在两种写法间混淆。面试时我还喜欢追问一句如果杨氏矩阵只有行递增、列没有递增关系能用这个解法吗不能。必须两个维度同时满足递增条件才成立。这能帮你验证候选人是不是真的理解算法原理而不只是背代码。3.2 旋转数组的最小数字题目把原数组旋转比如[1,2,3,4,5]变成[3,4,5,1,2]要求找最小值。表面看二分不能直接用因为数组不是全局有序。但它有一个特殊结构两段内部递增且前段所有元素大于后段所有元素。我的做法是比较nums[mid]与nums[right]。分三种情况。如果nums[mid]大于nums[right]说明mid一定在前段最小值在mid右侧left置为mid1。如果nums[mid]小于nums[right]说明mid及后半段递增最小值在mid左侧或就是midright置为mid。如果nums[mid]等于nums[right]比如[1,1,1,0,1]这时候无法判断属于哪一段稳妥的做法是right减一缩小范围继续比较。def min_in_rotated_array(nums): if not nums: return None left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] nums[right]: left mid 1 elif nums[mid] nums[right]: right mid else: right - 1 return nums[left]有一种更保守的实现是当nums[mid]、nums[left]、nums[right]三个值相等时放弃二分直接对区间做线性扫描。因为极端情况下二分无法确认最小值方向。把两种方案都讲给面试官说明你清楚局限是很好的加分表现。这道题还有一个隐藏加分点能不能顺手分析一下空间复杂度是O(1)以及为什么不用递归而用迭代。答案很简单迭代写法不需要额外的调用栈空间代码也更好调试。3.3 调整数组顺序使奇数位于偶数前面题目的要求很明确把数组里所有奇数放到偶数前面不要求保持原相对顺序但有经验的候选人应该主动问“是否要求相对顺序稳定”。如果不要求稳定用对撞指针left从左往右找偶数right从右往左找奇数找到就交换。如果要求稳定就用快慢指针慢指针j始终指向下一个奇数应该放置的位置快指针i遍历数组遇到奇数就把nums[i]和nums[j]交换然后j加一。由于所有奇数按原顺序被依次放到前面偶数顺序天然保持一致。def reorder_odd_even(nums): if not nums: return [] j 0 for i in range(len(nums)): if nums[i] % 2 1: nums[i], nums[j] nums[j], nums[i] j 1 return nums很多人写快慢指针版会犯一个错交换时写成只把奇数赋值给j偶数去向前搬结果数组里出现重复值。必须用元素交换而不是简单赋值。每次交换后nums[i]变成了原来的nums[j]它可能是偶数但这不影响后面继续扫描。这道题真正的高级技巧是“把判断奇偶的条件抽象出来”。我习惯把is_odd(num)设计成单独的函数这样题目改成“负数在正数前”“能被3整除的数在前”时只需要换一个判断函数整个算法骨架不用改动。这在真实开发里就是策略模式的一种极简体现面试官很吃这一套。3.4 顺时针打印矩阵一个m行n列的矩阵从左上角开始顺时针打印所有元素。比如3x4的矩阵打印顺序是第一行从左到右最后一列从上到下最后一行从右到左第一列从下到上然后缩进一圈继续重复。最直观的思路是模拟四个边界top、bottom、left、right。每次打印完一行或一列对应边界就向内收缩一位。关键难点在于当只有一行或一列时最后的“从右往左”“从下往上”可能和前面的打印重复。为了避免重复我在每一轮循环里加上条件判断。打印完上边后top加1打印完右边后right减1接下来如果top仍然小于等于bottom才打印下边如果left仍然小于等于right才打印左边。def spiral_order(matrix): if not matrix: return [] res [] top, bottom 0, len(matrix) - 1 left, right 0, len(matrix[0]) - 1 while top bottom and left right: for c in range(left, right 1): res.append(matrix[top][c]) top 1 for r in range(top, bottom 1): res.append(matrix[r][right]) right - 1 if top bottom: for c in range(right, left - 1, -1): res.append(matrix[bottom][c]) bottom - 1 if left right: for r in range(bottom, top - 1, -1): res.append(matrix[r][left]) left 1 return res拿一个只有一行、三列的矩阵试一下第一轮从左到右打印完整行top变成1随后for循环range(1, 2)不会执行right变成2但此时top大于bottom后续两个条件判断都为False就不会发生重复打印。考场上写这道题最稳的验证方式是随手画一个2x2的矩阵手动模拟一遍。2x2矩阵最容易暴露右下角和左下角同时被打印两次的问题。3.5 矩阵中的路径题目是这样给一个字符矩阵和一个字符串判断矩阵中是否存在一条路径使得路径上的字符依次构成这个字符串。要求路径不能重复经过同一个格子可以从任意格子出发方向限于上下左右。这是一道标准的回溯法题。我习惯把函数拆成两个部分外层遍历所有起点内层DFS搜索路径。def has_path(matrix, rows, cols, word): if not matrix or not word: return False visited [[False] * cols for _ in range(rows)] for i in range(rows): for j in range(cols): if dfs(matrix, rows, cols, i, j, word, 0, visited): return True return False def dfs(matrix, rows, cols, i, j, word, k, visited): if k len(word): return True if (i 0 or i rows or j 0 or j cols or visited[i][j] or matrix[i][j] ! word[k]): return False visited[i][j] True for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]: if dfs(matrix, rows, cols, i di, j dj, word, k 1, visited): return True visited[i][j] False return False这段代码里有三个关键位置需要特别上心。第一个是递归退出条件当k等于字符串长度时说明所有字符都匹配成功直接返回True不需要再判断当前格子是否越界。第二个是回溯重置在DFS返回前必须把visited[i][j]置回False否则一条失败路径会污染后续搜索。第三个是剪枝顺序越界、已访问、字符不匹配这三个判断最好一次性写完避免漏掉某个分支还能让代码更紧凑。面试时如果还有时间可以主动提一嘴空间复杂度visited数组O(m*n)递归调用栈最深O(len(word))。这会让面试官觉得你不是只会写代码而是对整个代价有感知。4. 实战中的高频问题与避坑记录4.1 边界条件最多的一类事故现场数组题里的Bug十有八九出在边界。多年下来我总结出一份高频边界清单每次模拟面试都会让候选人先过一遍空数组和空行。很多候选人在if not matrix之后就直接访问matrix[0]结果报错。正确姿势是同时确认行数和列数都大于0。单行和单列。比如顺时针打印矩阵只有一行时下边和左边的打印必须被条件拦住。只有一列时右边和底边的打印顺序也很容易重复。二分查找的mid计算。虽然主流语言里没有整数溢出问题但推荐统一写成mid left (right - left) // 2这能避免leftright在极端情况下溢出也更容易让面试官看懂。旋转数组里所有元素相同。比如[1,1,1,1]二分无法判断方向只能用right递减或线性扫描兜底不要硬套公式导致死循环。重复数字的交换死循环。原地交换时如果nums[i]和nums[nums[i]]相等说明已经找到重复数字需要立刻返回否则会无限交换。这些边界问题不是靠记忆力是靠练习量和手跑用例练出来的。面试时不要急着写代码先在草稿纸上画一个最小用例把索引变化走一遍再动手。4.2 复杂度误判别让“看着简单”害了你数组题特别容易让人产生复杂度错觉。我经常看到候选人刚说完暴力解法O(n^2)却答不上来为什么不能优化也碰到过有人把双指针写成O(n^2)还说自己是O(n)。正常的复杂度分析步骤是这样的先分析循环嵌套层数再看每个循环内的操作是否只执行常数时间。如果内部有哈希查找、二分查找这类O(log n)或O(1)操作要把它们计入整体。比如矩阵回溯每个格子最多访问一次每个格子展开四个方向复杂度是O(mn4)也就是O(m*n)但递归深度会带来额外栈空间。还有一个隐蔽问题原地交换数组时很多人以为psuh进结果列表会改变复杂度。实际上结果列表长度等于数组长度空间复杂度O(n)是必要的不算浪费。但如果题目要求O(1)额外空间你就不应该开辟这样的结果结构只能原地修改后返回原数组。给候选人一个简单自查标准写完后闭眼把自己的算法跑在三种用例上——最好情况、最坏情况、重复元素最多的极端情况。如果三种用例下的时间复杂度表现差异很大说明你还没有真正理解算法的本质。4.3 面试表达代码写完只是开始很多候选人把面试当成“写码现场”代码一通过样例就长舒一口气。但真实面试里代码写对只占一半分数另一半来自表达和验证。我的建议是拿到题先做三件事复述题目、确认约束、给出可选方案。复述题目能让面试官确认你没理解偏确认约束时要主动问“数组长度是多少”“允许修改原数组吗”“元素范围是什么”给出方案时要先说思路再写代码不要一上来就闷头敲。写代码之前可以先用一分钟在草稿纸上设计用例。一个普通用例、一个空用例、一个重复元素用例这三者在面试中几乎覆盖八成考察点。写完代码后手动拿着这个用例跑一遍不要只局限于样例。这个过程既帮助你发现边界Bug也给面试官展示你的调试思路。还有一个很多人的坏习惯自定义函数只有一长串逻辑没有把“判断条件”和“主流程”分开。比如“调整数组顺序”里把奇数判断内联在for循环里等题目一变就重写。我把这种习惯称为“代码的复用性差”在学习阶段就养成抽函数的习惯对做工程也很有帮助。4.4 快速自查速查表下面汇总了数组与矩阵篇最常考的题型和对应的最优思路我面试前习惯扫一眼这张表快速激活大脑。题目场景推荐思路时间复杂度关键注意点二维矩阵行列递增查找右上角或左下角出发逐次排除O(mn)两个维度都必须递增旋转数组找最小值二分比较mid与rightO(log n)相同元素时需右指针递减或线性兜底奇数在前偶数在后对撞指针或不稳定快慢指针求稳定O(n)用交换不要用覆盖顺时针打印矩阵模拟四边界收缩O(m*n)单行单列防重复打印矩阵中的路径DFS回溯O(m*n)visited必须回退数组中重复数字原地置换利用下标O(n)空间O(1)的前提是允许修改数组和为S的两个数字对撞指针O(n)前提是数组有序连续子数组最大和动态规划状态压缩O(n)理解“当前元素开新段还是续旧段”数组中的逆序对归并排序统计O(n log n)合并阶段统计右边小于左边的数量这张表不追求把所有题目都塞进去而是帮大家建立“看到题目先归到某个套路”的反射。数组题的量再多套路就这么多。最后再分享一点个人体会。我在带新人准备面试时经常强调一个词反射。看到数组题先反射性地想三件事能不能双指针能不能二分能不能原地修改。看到矩阵题先反射性地判断是模拟、回溯还是图论。这些反射建立之后你就不再需要每道题都从头推理而是快速匹配已知模式再根据边界细节做调整。剑指Offer数组与矩阵这部分我刷过不止三遍。第一遍是背题第二遍是总结套路第三遍才是真正理解了“为什么这样解”。希望你也能走到第三遍而不是停在“我看懂了答案”的幻觉里。