Hot 100这个题单，刷过的人应该都有体会：普通数组和矩阵专题看着基础，真正上手之后才发现水很深。数组牵扯到的前缀和、双指针、原地操作，矩阵牵扯到的坐标变换、边界控制、标记复用，几乎每一类都能被面试官拎出来当敲门砖。这篇文章不打算复述每道题的官方题解，而是把这个专题的套路拆开，告诉你为什么这些解法成立、哪些边界最容易踩坑、怎么把刷题经验转化成自己的解题框架。适合正在准备算法面试、或者想系统整理数组矩阵题型的人。从实际刷题效果来看，把这两块吃透，后面很多图论和动态规划题也会顺手不少，因为它们最终都落在数组和坐标操作上。
1. 为什么数组和矩阵值得单独拎出来刷
1.1 数组是所有数据结构的地基
数组是绝大多数数据结构的底层载体，树、图、堆在工程落地时基本都跑在一维数组上。面试里数组题并不只是考“会不会写循环”，而是在考你如何在有限空间里维护索引、压缩状态、控制遍历顺序。Hot 100的普通数组专题里，既有最大子数组和这种经典的动态规划入门题，也有接雨水这种看着就头疼的难题。把数组题刷明白，等于把这些底层能力一次性补齐。
我见过不少刷题的人一上来就啃动态规划、图论，结果碰到数组题反而翻车。原因很简单，数组题的坑往往很隐蔽，比如下标边界、空数组、负数、重复元素。这些细节在更复杂的数据结构里同样存在，但数组题最小、最容易暴露问题。先把数组题练稳，再往上层结构走，会轻松很多。
1.2 矩阵题考验的是二维拆分能力
矩阵从本质上说还是数组，只是多了一层行列关系。普通数组的思维惯性放到矩阵里很容易失灵，因为你会同时面对行、列、方向、边界四个变量。比如螺旋矩阵要求你按右、下、左、上的方向转圈输出，旋转图像要求你把坐标映射做对，矩阵置零要求你不开额外数组完成标记。这些问题的核心都是同一个：把二维的变化拆成一组一维的规则。
所以我在刷题时会把普通数组和矩阵分开总结。普通数组的套路集中在前缀和、双指针、原地操作；矩阵的套路集中在坐标变换、方向控制、状态复用。分开刷的好处是你能更清楚地看到每种题型的共性，而不是把一堆题目混在一起，最后只记住了题目本身，没记住解法逻辑。
2. 普通数组专题：核心套路与典型题拆解
2.1 前缀和：子数组问题的最优解
凡是“连续子数组的和满足某个条件”的题目，都可以优先想到前缀和。以“和为K的子数组”为例，暴力解法是枚举所有起点和终点，时间复杂度O(n²)，数据量一大必然超时。用前缀和，我们可以把子数组和sum[i..j]转化为pre[j] - pre[i-1]，这样问题就变成了“统计pre中相差K的配对数量”。
实际实现时不需要真的维护一整个前缀和数组，只要在遍历过程中用一个哈希表记录当前前缀和的出现次数，然后查询cur_sum - K是否出现过。这里有一个非常容易踩的坑：初始化时一定要把前缀和0的次数设为1。否则从数组开头开始的子数组会被漏掉。我在第一次写这道题的时候就是漏了这个，结果后面的测试用例一直少几个答案。
from collections import defaultdict def subarray_sum(nums, k): prefix = defaultdict(int) prefix[0] = 1 cur = 0 ans = 0 for x in nums: cur += x ans += prefix.get(cur - k, 0) prefix[cur] += 1 return ans2.2 双指针：夹逼和去重的艺术
双指针在数组题里主要干两件事：一是利用有序性夹逼寻找组合，比如三数之和；二是维护一个滑动区间，比如合并区间。
三数之和是Hot 100里非常经典的题目。直接三层循环不是不能做，而是去重太痛苦。更稳的做法是排序之后固定一个数，再用左右指针夹逼。这里有两个关键点：外层循环遇到重复元素要跳过，指针移动时也要跳过重复元素，否则结果里会出现大量重复三元组。剪枝方面，如果固定数已经大于0，可以直接结束，因为后面的数都比它大。
def three_sum(nums): nums.sort() n = len(nums) res = [] for i in range(n): if nums[i] > 0: break if i > 0 and nums[i] == nums[i - 1]: continue lo, hi = i + 1, n - 1 while lo < hi: s = nums[i] + nums[lo] + nums[hi] if s == 0: res.append([nums[i], nums[lo], nums[hi]]) while lo < hi and nums[lo] == nums[lo + 1]: lo += 1 while lo < hi and nums[hi] == nums[hi - 1]: hi -= 1 lo += 1 hi -= 1 elif s < 0: lo += 1 else: hi -= 1 return res合并区间则更依赖对边界的处理。先把区间按起始位置排序，然后逐个检查当前区间的end是否大于等于下一个区间的start。如果是，就合并并更新end；否则把当前区间加入结果，切换新区间。这道题的难点不在算法，而在你能否在边界比较时保持逻辑清晰，尤其是相等的情况，别漏合并。
2.3 原地操作：空间复杂度O(1)的硬要求
Hot 100里不少数组题都要求原地操作。轮转数组看起来只是把数组往右移k步，但很多人第一反应是开一个新数组，这在面试里往往不是最优解。优先想到三次反转：先整体反转，再反转前k个，再反转后k个。注意要先对k取余，因为k可能大于数组长度。
def rotate(nums, k): n = len(nums) k %= n nums.reverse() nums[:k] = reversed(nums[:k]) nums[k:] = reversed(nums[k:])除自身以外数组的乘积是另一个典型。题目要求不能用除法，最好O(1)额外空间。思路是先用输出数组保存每个位置左边的乘积，再从右往左遍历，用一个变量维护右边的乘积，乘到输出数组上。这个思路很多第一次刷的人想不到，但一旦理解了“左一遍右一遍”的设计，很多数组题都有类似套路。
2.4 容易被忽略的细节题
最大子数组和虽然是动态规划题，但本质还是数组状态推导，状态转移方程cur = max(x, cur + x)很简单。缺失的第一个正数这道题比较特殊，思维上要绕一个弯：把数组自己当成哈希表，把数字i放到下标i-1的位置上，然后再扫描一遍找第一个对不上的位置。这类“数组本身做标记”的思路，在普通数组专题和矩阵专题里都会反复出现。
3. 矩阵专题：坐标变换与边界控制的实战要点
3.1 螺旋矩阵：方向控制的核心模板
螺旋矩阵是我觉得矩阵题里最需要画图的一道。很多人写得出来，但一到边界就乱，原因在于没有把循环不变量定清楚。我的做法是维护top、bottom、left、right四个边界，每次走完一条边就收缩对应的边界。注意在走完向右和向下之后，要检查top <= bottom和left <= right，否则矩阵是单行或单列时会重复输出。
def spiral_order(matrix): res = [] 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 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 res3.2 旋转图像：坐标映射要画图
旋转图像要求将n×n矩阵顺时针旋转90度。最不容易出错的做法是分两步：先沿主对角线转置，再对每一行做左右翻转。这个做法每一步都很直观，而且不容易把坐标算错。如果非要原地四角交换，就需要小心翼翼推导i和j的映射关系，很容易出错。
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 row in matrix: row.reverse()3.3 矩阵置零：用第一行第一列做标记
矩阵置零的常规思路是扫描到0，然后把对应行和列的所有位置都置0。但这样做会导致后续遍历时把原本不是0的位置也当成0的来源。正确解法是用第一行和第一列作为标记位，提前记录第一行和第一列本身是否有0，然后从第二行第二列开始扫描，用第一行第一列记录该行该列是否需要清零，最后再处理第一行和第一列。
这个题特别容易栽在最后一步：如果不小心先把第一行或者第一列清了，标记信息就全丢了。我建议按“先记录、再打标、最后按标记清0”的顺序来写，每一步做什么都很明确。
def set_zeroes(matrix): m, n = len(matrix), len(matrix[0]) row_zero = any(matrix[0][j] == 0 for j in range(n)) col_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 row_zero: for j in range(n): matrix[0][j] = 0 if col_zero: for i in range(m): matrix[i][0] = 03.4 有序矩阵与图类矩阵问题
搜索二维矩阵 II是矩阵里性价比很高的一道题。矩阵每行从左到右递增，每列从上到下递增。暴力遍历当然可以，但最优解是从右上角开始，如果当前值大于target就往左走，小于target就往下走。这样每一步都能排除一整行或一整列，时间复杂度是O(m+n)。这个思路很像双指针，只是把一维的夹逼搬到了二维。
岛屿数量则是矩阵和图的交叉题。核心是DFS或BFS，每遇到一个“1”就计数加一，然后把它能连到的所有“1”都改成“0”，避免下次重复统计。实现时要注意递归的边界条件，以及是否允许修改原数组。如果不能修改原数组，就要用visited矩阵来标记，代价是额外空间。
4. 从真题实操到代码模板：手把手过一遍
4.1 一道题从读题到AC的完整路径
以“除自身以外数组的乘积”为例，完整走一遍思考过程。题目要求输出每个位置除自身以外所有元素的乘积，且不能用除法，最好做到O(n)时间和O(1)额外空间。
第一步，先想到暴力：每个位置都重新算一遍乘积，复杂度O(n²)。虽然能过小样例，但显然不是目标。
第二步，想到用前缀积数组保存每个位置左边的累积乘积，再事后用后缀积乘回来，需要两个额外数组，空间O(n)。这个办法已经能解决问题，但还不够优化。
第三步，把左边的乘积直接写在输出数组里，然后从右往左遍历，用一个变量累计右边的乘积，乘到res[i]上。输出数组不算额外空间，所以整体空间O(1)。
def product_except_self(nums): n = len(nums) res = [1] * n left = 1 for i in range(n): res[i] = left left *= nums[i] right = 1 for i in range(n - 1, -1, -1): res[i] *= right right *= nums[i] return res4.2 高频代码模板汇总
除了上面已经给出的模板，还有几个值得背下来的片段。
最大子数组和的状态压缩写法：
def max_sub_array(nums): cur = best = nums[0] for x in nums[1:]: cur = max(x, cur + x) best = max(best, cur) return best搜索二维矩阵 II的右上角启动写法：
def search_matrix(matrix, target): if not matrix: return False m, n = len(matrix), len(matrix[0]) i, j = 0, n - 1 while i < m and j >= 0: if matrix[i][j] == target: return True if matrix[i][j] > target: j -= 1 else: i += 1 return False岛屿数量的沉岛DFS写法：
def num_islands(grid): def dfs(i, j): if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == "0": return grid[i][j] = "0" dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) ans = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == "1": ans += 1 dfs(i, j) return ans模板不需要死记，但你要清楚每行代码在做什么，尤其是边界判断。不然面试时很容易因为一个小条件写错，整段逻辑崩盘。
4.3 时间复杂度和空间复杂度的取舍
刷题的时候我习惯把每道题的暴力解和优化解开一张对照表，方便快速回忆。比如：
| 题目类型 | 暴力思路 | 优化思路 | 最终复杂度 |
|---|---|---|---|
| 子数组和为K | 枚举两端点 | 前缀和+哈希表 | O(n) |
| 三数之和 | 三层循环 | 排序+双指针 | O(n²) |
| 轮转数组 | 新数组拷贝 | 三次反转 | O(n) |
| 矩阵置零 | 额外行列标记 | 第一行第一列标记 | O(1)空间 |
| 搜索二维矩阵 | 全量遍历 | 右上角折线搜索 | O(m+n) |
面试时优先给出优化解，但别把暴力解丢掉。很多时候面试官会先让你说思路，再问能不能优化。如果你只背了最终解法，反而容易被追问卡住。
5. 常见问题与排查技巧实录
5.1 超时：别让O(n²)拖垮你
数组题超时最常见的诱因就是双重循环。三数之和如果不用排序加双指针，而是三层循环硬算，大概率超时。和为K的子数组如果不做前缀和，只在原地枚举起点和终点，也会在数据量大时挂掉。
排查思路很简单：先确认你的算法时间复杂度是不是O(n²)或更差，再看题目给的数据范围。如果数据规模超过10⁵，O(n²)基本没戏。这时候应该往哈希表、双指针、排序剪枝方向想。如果用了这些优化还是超时，再看是不是没有提前break或continue，导致无谓的遍历。
5.2 越界：边界变量是矩阵题的重灾区
矩阵题的越界才是高频事故。螺旋矩阵少了方向上的边界检查，单行单列就会重复输出。旋转图像的坐标公式写错，4x4矩阵就会错位。轮转数组忘记取余，k超过n时结果完全不对。
我处理这类问题的方法是手动模拟小用例，用3x3或4x4的矩阵把每一步写下来，对照代码走一遍。走两遍基本就能定位是哪个变量在哪个方向更新错了。
5.3 漏解和重复解：去重逻辑要反复推敲
三数之和最容易出的问题就是结果重复。外层跳过了重复固定数，但内层指针如果没跳过重复移动值，仍然会产生重复。反向的漏解也常见，比如固定数大于0时没有及时break，虽然那样不会重复，但会拖慢速度。
前缀和题也容易漏解，就是前面说的map[0] = 1漏掉。另外一个常踩的坑是哈希表的更新顺序：先查再更新，顺序反了会把当前元素重复算进去。这些问题靠背是很难记牢的，只有真正手写几遍、被测试用例教训几次，才会形成条件反射。
5.4 面试中减少翻车的几个小习惯
几个我长期坚持的习惯：读题后先确认输入范围、是否允许修改原数组、空间复杂度要求。很多题如果允许修改原数组，解法会简单很多，比如岛屿数量可以直接沉岛，矩阵置零可以用第一行第一列打标。如果不允许，就需要额外空间或者更复杂的标记方式。
写代码之前，先在脑内或者纸上过一个小用例，把关键边界条件写清楚。写完代码后，不要马上提交，手动跑一遍示例，再跑一遍极端用例，比如空数组、单元素数组、全0矩阵。这样做看起来多花了几分钟，但能避免大量低级错误。
数组和矩阵专题刷下来，我最明显的感觉是：这两块不是靠题海堆出来的，而是靠“复盘套路”堆出来的。每道题做完之后，我都强迫自己回答三个问题：这个解法为什么能成立？如果换一组数据边界，它还会不会成立？这个套路还能用到哪些题上？回答完这三个问题，一道题才算真正吃透。
最后再分享一个小技巧：遇到矩阵题先画图，遇到数组题先列状态。画图不是浪费时间，坐标变换和边界控制这类问题，光靠脑内模拟很容易漏掉方向变化。列状态则是把“当前我手里有什么变量、下一步要更新谁”写清楚，很多卡壳其实是因为变量没理顺。这两个习惯看起来笨，但实际刷题效率反而最高。
