知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 前缀和模板 ## 什么是前缀和 前缀和就是"从头加到当前位置的累加和"。提前算好存起来,之后任意区间的和都能 O(1) 算出来。 ``` 原数组: [2, 1, 5, 3, 4] 前缀和:[0, 2, 3, 8, 11, 15] ↑ 多一个 0,方便计算 区间 [1,3] 的和 = prefix[4] - prefix[1] = 11 - 2 = 9 验证:1 + 5 + 3 = 9 ✓ ``` 公式:`sum(i, j) = prefix[j+1] - prefix[i]` ## 一维前缀和 ```java // 构建 int[] prefix = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { prefix[i + 1] = prefix[i] + nums[i]; } // 查询区间 [left, right] 的和 int rangeSum = prefix[right + 1] - prefix[left]; ``` 为什么长度是 n+1?多出来的 `prefix[0] = 0` 让公式统一,不用特判 left=0 的情况。 ## 二维前缀和 ``` 原矩阵: 前缀和矩阵: 1 2 3 0 0 0 0 4 5 6 0 1 3 6 7 8 9 0 5 12 21 0 12 27 45 prefix[i][j] = 从 (0,0) 到 (i-1,j-1) 的矩形区域和 ``` ```java // 构建 int[][] prefix = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]; // 减去重复加的部分 } } // 查询 (r1,c1) 到 (r2,c2) 的矩形区域和 int sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]; ``` ``` 容斥原理: ┌─────────┬─────┐ │ A │ B │ ├─────────┼─────┤ 目标区域 D 的和 = 整体 - A列 - B行 + 左上角(被减了两次) │ C │ D │ └─────────┴─────┘ ``` ## 前缀和 + HashMap 模式 很多题不是直接求区间和,而是"有多少个子数组的和等于 k"。 ``` 如果 prefix[j] - prefix[i] == k 那么 prefix[i] == prefix[j] - k 用 HashMap 记录每个前缀和出现的次数 遍历到 j 时,查 HashMap 中 prefix[j] - k 出现了几次 ``` 这个模式在第 02~05 题中反复使用。 > 💬 **Q:举例说明前缀和 + HashMap 模式** > > 用 `nums = [1, 2, 3, -1, 2]`,`k = 4` 演示完整过程: > > ``` > 前缀和数组: > index: 0 1 2 3 4 5 > nums: 1 2 3 -1 2 > prefix: 0 1 3 6 5 7 > > 初始化 map = {0: 1}(前缀和 0 出现 1 次,处理从头开始的子数组) > > j=1, curSum=1:查 1-4=-3 → 没有。map: {0:1, 1:1} > j=2, curSum=3:查 3-4=-1 → 没有。map: {0:1, 1:1, 3:1} > j=3, curSum=6:查 6-4=2 → 没有。map: {0:1, 1:1, 3:1, 6:1} > j=4, curSum=5:查 5-4=1 → 有!count=1(子数组 [2,3,-1],下标 1~3) > j=5, curSum=7:查 7-4=3 → 有!count=2(子数组 [3,-1,2],下标 2~4) > > 最终答案:2 个子数组 > ``` > > 关键理解:`prefix[j] - prefix[i] = k` 等价于 `prefix[i] = prefix[j] - k`。遍历到 j 时,`prefix[j]` 和 `k` 都已知,只需查 map 里有没有值等于 `prefix[j] - k` 的前缀和,有几个就说明有几个以 j 结尾的合法子数组。 ## 一句话总结 前缀和把区间求和从 O(n) 优化到 O(1)。配合 HashMap 可以解决"子数组和等于 k"类问题。 --- 下一篇:[02 - 和为K的子数组](./02-subarray-sum-k.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入