03 · 数组与矩阵
来源： labuladong 数组技巧 + 代码随想录数组专题
核心价值： 掌握数组原地操作技巧与矩阵遍历模式
一、本质理解
数组的本质是连续内存空间，支持 O(1) 随机访问，但插入/删除需要 O(n) 移动元素。
矩阵是二维数组，底层也是连续存储（行优先）。
二、数组核心技巧
1. 前缀和（区间和问题）
def prefix_sum(nums):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
# 区间 [i, j] 的和 = prefix[j+1] - prefix[i]
return prefix适用场景： 需要频繁计算子数组和 → 01-哈希表 模板 4
2. 差分（区间增减问题）
def difference(nums, updates):
# updates: [[l, r, val], ...]
diff = [0] * (len(nums) + 1)
for l, r, val in updates:
diff[l] += val
diff[r + 1] -= val
# 还原
for i in range(len(nums)):
diff[i + 1] += diff[i]
nums[i] += diff[i]
return nums3. 原地操作（空间 O(1)）
三次翻转法 — 轮转数组：
def rotate(nums, k):
k %= len(nums)
# 整体翻转
nums.reverse()
# 前 k 个翻转
nums[:k] = reversed(nums[:k])
# 后 n-k 个翻转
nums[k:] = reversed(nums[k:])前缀积 + 后缀积 — 除自身以外数组的乘积：
def product_except_self(nums):
n = len(nums)
res = [1] * n
# 前缀积
prefix = 1
for i in range(n):
res[i] = prefix
prefix *= nums[i]
# 乘上后缀积
suffix = 1
for i in range(n - 1, -1, -1):
res[i] *= suffix
suffix *= nums[i]
return res原地哈希 — 缺失的第一个正数：
def first_missing_positive(nums):
n = len(nums)
# 把值 x 放到索引 x-1 的位置
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
# 找第一个不匹配的位置
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 14. Kadane 算法（最大子数组和）
def max_sub_array(nums):
cur_sum = max_sum = nums[0]
for num in nums[1:]:
cur_sum = max(num, cur_sum + num)
max_sum = max(max_sum, cur_sum)
return max_sum三、矩阵核心技巧
1. 螺旋遍历（边界收缩法）
def spiral_order(matrix):
res = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# 向右：左 → 右
for i in range(left, right + 1):
res.append(matrix[top][i])
top += 1
# 向下：上 → 下
for i in range(top, bottom + 1):
res.append(matrix[i][right])
right -= 1
if top <= bottom:
# 向左：右 → 左
for i in range(right, left - 1, -1):
res.append(matrix[bottom][i])
bottom -= 1
if left <= right:
# 向上：下 → 上
for i in range(bottom, top - 1, -1):
res.append(matrix[i][left])
left += 1
return res2. 旋转图像（转置 + 翻转）
def rotate_matrix(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):
matrix[i].reverse()3. 矩阵置零（原地标记法）
def set_zeroes(matrix):
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_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 first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 04. 搜索二维矩阵（右上角搜索法）
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
row, col = 0, cols - 1 # 右上角出发
while row < rows and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1
else:
row += 1
return False四、Hot 100 数组与矩阵题目清单
| 题号 | 题目 | 难度 | 核心技巧 | 建议用时 |
|---|---|---|---|---|
| 53 | 最大子数组和 | Medium | Kadane 算法 | 25 min |
| 56 | 合并区间 | Medium | 排序 + 扫描 | 30 min |
| 189 | 轮转数组 | Medium | 三次翻转法 | 25 min |
| 238 | 除自身外乘积 | Medium | 前缀积+后缀积 | 30 min |
| 41 | 缺失的第一个正数 | Hard | 原地哈希 | 40 min |
| 73 | 矩阵置零 | Medium | 原地标记 | 30 min |
| 54 | 螺旋矩阵 | Medium | 边界收缩 | 35 min |
| 48 | 旋转图像 | Medium | 转置+翻转 | 25 min |
| 240 | 搜索二维矩阵 II | Medium | 右上角搜索 | 30 min |
五、易错点与技巧
- 边界条件：矩阵题中始终注意
row和col的范围，以及空矩阵的特殊情况 - 原地操作：想修改原数组时，先问自己”会不会覆盖还没用的数据”
- 取模运算：轮转数组
k %= len(nums)处理 k > n 的情况 - 原地哈希：用数组本身的索引作为哈希 key，值作为标记，空间 O(1)
六、参考与延伸
- 02-双指针与滑动窗口（Kadane 算法和双指针相关）
- 09-二分查找（搜索二维矩阵可用二分）
- labuladong 数组技巧：https://labuladong.online/algo/