尧图网站建设 
教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载LogicStack-LeetCode是公众号「宫水三叶的刷题日记」的刷穿 LeetCode 系列题解仓库其 Index/前缀和.md 是一份覆盖 50 道 LeetCode 题目的「前缀和」专题索引表横跨简单、中等、困难三个难度档位。本文以该索引表为骨架逐类拆解前缀和的核心原理、通用模板并从仓库 LeetCode/ 目录中选取最具代表性的题解源码深入讲解「一维前缀和」「二维前缀和」「前缀和 哈希表」「前缀异或」「前缀和 二分」等实战套路让读者既看得懂公式也拿得到可以直接运行的多语言模板。前缀和是什么从「暴力求和」到「O(1) 区间查询」在 303. 区域和检索 - 数组不可变 与 53. 最大子数组和 两篇题解中仓库给出了前缀和的统一定义所谓前缀和是指对原数组“累计和”的描述通常是指一个与原数组等长的数组。设前缀和数组为sumsum的每一位记录的是从「起始位置」到「当前位置」的元素和。例如sum[x]是指原数组中“起始位置”到“位置x”这一连续段的元素和。有了前缀和数组sum求连续段[i, j]的区域和时利用「容斥原理」即可快速求解通用公式为ans sum[j] - sum[i - 1]之所以要求连续段区域和时“要很自然想到前缀和”是因为它把原本每次O(len)的区间求和变成了预处理一次、之后每次O(1)的查询本质上是“用预处理空间换查询时间”的典型交换。下标偏移从 0 开始的原数组与从 1 开始的前缀和仓库题解中反复强调一个实现细节由于公式涉及i - 1操作为减少边界处理让前缀和数组下标从 1 开始查询时再根据原数组下标是否从 1 开始决定是否进行下标偏移。以 303. 区域和检索 - 数组不可变 的 Java 实现为例class NumArray { int[] sum; public NumArray(int[] nums) { int n nums.length; // 前缀和数组下标从 1 开始因此设定长度为 n 1模板部分 sum new int[n 1]; // 预处理前缀和数组模板部分 for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; } public int sumRange(int i, int j) { // 求某一段区域和 [i, j] 的模板是 sum[j] - sum[i - 1]模板部分 // 但由于源数组下标从 0 开始因此要在模板的基础上进行 1 i; j; return sum[j] - sum[i - 1]; } }仓库原文特意用「模板部分」标注了两处最值得记忆的骨架代码预处理时sum[i] sum[i - 1] nums[i - 1]查询时先i; j再return sum[j] - sum[i - 1]。只要记住这两行一维前缀和的绝大多数裸题都能直接套用。一维前缀和模板多语言仓库在 303. 区域和检索 - 数组不可变 中整理了一维前缀和的最小模板Java 为例// 预处理前缀和数组 { sum new int[n 1]; for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; } // 计算 [i, j] 结果 { i; j; ans sum[j] - sum[i - 1]; }同一份模板在仓库中给出了 Java、C、Python、TypeScript 四种实现写法完全对齐方便在任意语言环境下直接对照移植。模板的底层本质容斥与 DP该模板之所以正确底层依据有二仓库 303 题解 的「总结」一节有明确说明数学/容斥视角某一段的区间和 起点到区间右端点的和含右端点− 起点到区间左端点的和不含左端点DP 视角前缀和的每一位都依赖「前一位置的前缀和」与「当前位置的原数组值」求解过程类似 509. 斐波那契数 的递推属于最朴素的线性 DP。前缀和的第一个变体一维滚动优化求最大子数组和53最大子数组和 是索引表中推荐指数达 的经典题Tag 为「前缀和 / 区间求和问题 / 线性 DP / 分治」。仓库给出的核心思路是先用nums预处理出前缀和数组sum然后在遍历子数组右端点j的过程中通过变量m动态记录已访问的左端点i的前缀和最小值最终在所有sum[j] - m的取值中选取最大值作为答案。代码实现上无需显式构造sum数组直接用变量s表示当前累计前缀和右端点用m记录已访问前缀和的最小值左端点class Solution { public int maxSubArray(int[] nums) { int s 0, m 0, ans -10010; for (int x : nums) { s x; ans Math.max(ans, s - m); m Math.min(m, s); } return ans; } }时间复杂度O(n)、空间复杂度O(1)。仓库同时指出这道题除了「前缀和裸题 有限变量空间优化」的角度还能以线性 DP理解定义f[i]为考虑前i个元素且第nums[i]必选时形成的最大子数组和转移方程为f[i] max(f[i - 1] nums[i], nums[i])由于f[i]只依赖f[i - 1]同样可用有限变量优化写出的代码与前缀和角度几乎一致——两种视角殊途同归是理解前缀和与 DP 关系的最佳样本。进阶分治解法仓库还给出了本题的分治解法Tag 同样包含「分治」递归函数签名设计为int[] dfs(int[] nums, int l, int r)返回值是四元组[sum, lm, rm, max]分别代表「区间和、前缀最大值、后缀最大值、最大子数组和」。合并规则仓库原文待合并信息合并公式区间和sumsum left[0] right[0]前缀最大值lmlm max(left[1], left[0] right[1])后缀最大值rmrm max(right[2], right[0] left[2])最大子数组和maxmax max(left[3], right[3], left[2] right[1])一个需要特别处理的细节lm、rm、max在计算时允许空数组因此当nums全为负数时分治会错误得出最大子数组和为0的答案。仓库的做法是遍历一遍nums若最大值为负数则直接返回该最大值。分治版时间复杂度O(n)、空间复杂度O(log n)。前缀和 哈希表统计和为 K 的子数组个数560和为 K 的子数组 是推荐指数 的前缀和经典题Tag 为「前缀和 / 哈希表」。核心思路仓库原文统计以每一个nums[i]为结尾、和为k的子数组数量即是答案。预处理前缀和数组sum下标从 1 开始后对以nums[i]结尾的区间本质是求在[0, i]中sum数组里有多少个值为sum[i 1] - k的数——这可以在遍历过程中用「哈希表」同步记录每个前缀和值出现的次数class Solution { public int subarraySum(int[] nums, int k) { int n nums.length, ans 0; int[] sum new int[n 10]; for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; MapInteger, Integer map new HashMap(); map.put(0, 1); // 前缀和为 0 出现过一次对应「空子数组」 for (int i 1; i n; i) { int t sum[i], d t - k; ans map.getOrDefault(d, 0); map.put(t, map.getOrDefault(t, 0) 1); } return ans; } }注意map.put(0, 1)这一行它代表“前缀和为 0 在位置 0 出现过一次”用于正确统计「从下标 0 开始的子数组」是哈希表变体中容易遗漏的初始化。时间复杂度O(n)、空间复杂度O(n)。前缀和的哨兵技巧寻找数组的中心下标724寻找数组的中心下标 是一道前缀和裸题仓库给出了三档空间优化非常适合用来演示前缀和的不同写法写法一前后两遍前缀和 哨兵。为简化数组越界判断前缀和数组多预留一位作为哨兵本题需要前后两个方向的前缀和因此直接多开两位class Solution { public int pivotIndex(int[] nums) { int n nums.length; int[] s1 new int[n 2], s2 new int[n 2]; for (int i 1; i n; i) s1[i] s1[i - 1] nums[i - 1]; for (int i n; i 1; i--) s2[i] s2[i 1] nums[i - 1]; for (int i 1; i n; i) { if (s1[i] s2[i]) return i - 1; } return -1; } }写法二一遍前缀和。只处理一遍前缀和判定某个下标是否为“中心下标”时用前缀和现场计算左侧值与右侧值left sum[i - 1]right sum[n] - sum[i]。仓库指出这只是常数级别的优化不改变时空复杂度。写法三优化至 O(1) 空间。先求一遍总和total再用sum记录当前遍历位置的左侧总和中心下标必然满足sum total - sum - nums[i]左边值 右边值无需任何额外数组class Solution { public int pivotIndex(int[] nums) { int n nums.length, total 0, sum 0; for (int i 0; i n; i) total nums[i]; for (int i 0; i n; i) { if (sum total - sum - nums[i]) return i; sum nums[i]; } return -1; } }前缀和的容斥变体除自身以外数组的乘积238除自身以外数组的乘积 的 Tag 是「前缀和 / 容斥原理」但它实际用的是前缀乘与后缀乘——这是“前缀和思想”在乘法语境下的直接迁移。对每个ans[i]其值由两部分组成(nums[0] × nums[1] × ... × nums[i - 1]) × (nums[i 1] × nums[i 2] × ... × nums[n - 1])因此用s1记录范围[1, x]的前缀乘s2记录范围[x, n]的后缀乘然后ans[i - 1] s1[i - 1] × s2[i 1]。仓库还给出了空间优化版直接复用ans数组先从左到右累乘前缀部分再从右到左累乘后缀部分最终空间复杂度降为O(1)输出数组不计入额外空间。这道题与 53 题 一起说明了前缀和的“可迁移性”只要某个答案能拆成“前缀部分 × 后缀部分”或和/差/异或前缀和思想就能以 O(1) 查询的代价解决它。二维前缀和矩阵区域求和与容斥公式304二维区域和检索 - 矩阵不可变 是「二维前缀和」裸题推荐指数 。仓库给出了清晰的定义二维前缀和数组中的每一个格子记录的是「以当前位置为区域的右下角区域左上角恒定为原数组的左上角的区域和」。预处理公式sum[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i - 1][j - 1] matrix[i - 1][j - 1]查询左上角(x1, y1)、右下角(x2, y2)的区域和公式容斥sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] sum[x1 - 1][y1 - 1]完整 Java 实现仓库原文class NumMatrix { int[][] sum; public NumMatrix(int[][] matrix) { int n matrix.length, m n 0 ? 0 : matrix[0].length; // 与「一维前缀和」一样前缀和数组下标从 1 开始模板部分 sum new int[n 1][m 1]; // 预处理前缀和数组模板部分 for (int i 1; i n; i) { for (int j 1; j m; j) { sum[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i - 1][j - 1] matrix[i - 1][j - 1]; } } } public int sumRegion(int x1, int y1, int x2, int y2) { // 求区域和模板sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] sum[x1 - 1][y1 - 1]模板部分 // 由于源数组下标从 0 开始先全部 1 x1; y1; x2; y2; return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] sum[x1 - 1][y1 - 1]; } }时间复杂度预处理O(n * m)单次查询O(1)空间复杂度O(n * m)。二维前缀和模板记忆法仓库在 304 题解 中分享了一套口诀式的记忆法预处理当前格子(和) 上方的格子(和) 左边的格子(和) − 左上角的格子(和) 当前格子(值)查询先把原数组坐标全部 1 转为前缀和坐标然后记作22 − 12 − 21 11即sum[x2][y2]减去x1-1行、y1-1列再加回减重的左上角(x1-1, y1-1)。二维前缀和的延伸题索引表中与二维前缀和强相关的题目还有最大矩形在二维前缀和/单调栈基础上求解最大全 1 矩形元素和为目标值的子矩阵数量枚举矩阵上下边界后用一维前缀和 哈希表统计矩形区域不超过 K 的最大数值和二维前缀和结合有序集合优化枚举找出第 K 大的异或坐标值二维异或前缀和 排序/堆。前缀异或把容斥从减法换成异或1310子数组异或查询 展示了前缀和思想在“异或”语境下的迁移Tag 为「数学 / 树状数组 / 前缀和」。仓库的核心结论xor(l, r) xor(1, r) ⊕ xor(1, l - 1)本质上还是利用集合区间结果的容斥原理。只不过前缀和需要利用「减法逆运算」做容斥而前缀异或是利用「相同数值进行异或结果为 0偶数次的异或结果为 0」的特性实现容斥。前缀异或实现class Solution { public int[] xorQueries(int[] arr, int[][] qs) { int n arr.length, m qs.length; int[] sum new int[n 1]; for (int i 1; i n; i) sum[i] sum[i - 1] ^ arr[i - 1]; int[] ans new int[m]; for (int i 0; i m; i) { int l qs[i][0] 1, r qs[i][1] 1; ans[i] sum[r] ^ sum[l - 1]; } return ans; } }时间复杂度O(n m)、空间复杂度O(n)。仓库还顺带对比了「树状数组」与「前缀异或」本题不涉及修改操作因此无需树状数组前缀异或即可把查询复杂度从O(log n)降到O(1)。此外仓库在本题中总结了“区间求值问题”的方案选型表极具实战价值场景可选方案数组不变求区间和前缀和、树状数组、线段树多次修改某个数求区间和树状数组、线段树多次整体修改某个区间求区间和线段树、树状数组视修改区间数据范围而定多次将某个区间变成同一个数求区间和线段树、树状数组结论线段树能解决的问题最多但代码长、常数大只有在不得不用时才考虑。索引表中的异或前缀和相关题目还包括 1442. 形成两个异或相等数组的三元组数目异或前缀和 枚举、1738. 找出第 K 大的异或坐标值二维异或前缀和。前缀和 二分利用单调性把 O(n²) 降为 O(n log n)209长度最小的子数组 的 Tag 为「前缀和 / 二分 / 滑动窗口」。因为nums[i]的取值范围是[1, 10^5]全为正数前缀和数组天然满足单调递增具备二段性可以二分。核心思路仓库原文对每个nums[i]视作子数组右端点其前缀和值为s sum[i 1]问题转换为在前缀和数组下标[0, i]范围内找到满足「值小于等于s - t」的最大下标充当子数组左端点的前一个位置。二分采用“找右边界”写法l mid 1分支在sum[mid] d时成立class Solution { public int minSubArrayLen(int t, int[] nums) { int n nums.length, ans n 10; int[] sum new int[n 10]; for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; for (int i 1; i n; i) { int d sum[i] - t; int l 0, r i; while (l r) { int mid l r 1 1; if (sum[mid] d) l mid; else r mid - 1; } if (sum[r] d) ans Math.min(ans, i - r); } return ans n 10 ? 0 : ans; } }时间复杂度O(n log n)、空间复杂度O(n)。仓库同时给出滑动窗口解法复杂度可降到O(n)、空间O(1)——两种解法并存正好演示“前缀和擅长利用单调性做二分滑动窗口则直接在原数组上维护窗口和”。前缀和的多场景组合索引表全景导读回到 Index/前缀和.md 这份索引表本身50 道题几乎覆盖了前缀和的所有组合形态可按下表快速定位适合自己的练习路线场景 / 组合代表题仓库路径一维前缀和裸题区间求和303、724、1480、1588LeetCode 对应目录前缀和 哈希表计数/最长560、525、930、523、437LeetCode 对应目录前缀和 二分 / 单调性209、1208、1838LeetCode 对应目录二维前缀和容斥304、85、1074、363LeetCode 对应目录前缀异或异或容斥1310、1442、1738LeetCode 对应目录前缀乘容斥变体238LeetCode/231-240前缀和滚动优化有限变量53、396、1749LeetCode 对应目录前缀和 排序 / 双指针327、825、689LeetCode 对应目录前缀和 差分区间增量1094、1109、2055、2100LeetCode 对应目录前缀和 随机 / 权重采样497、528、710LeetCode 对应目录剑指 Offer / LCR 系列剑指 Offer II 008、剑指 Offer II 010、剑指 Offer II 011、LCR 161同 53LeetCode/剑指 Offer II、LeetCode/LCR索引表中其余题目如 187. 重复的DNA序列、926. 将字符串翻转到单调递增、1154. 一年中的第几天 之外的对应目录、629. K个逆序对数组、661. 图片平滑器、1422. 分割字符串的最大得分、1537. 最大得分、1652. 拆炸弹、1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗、1894. 找到需要补充粉笔的学生编号、1004. 最大连续1的个数 III则分别从字符串前缀统计、双指针、枚举等角度复用同一套“累计和 容斥”思想难度档位从简单到困难递进可作为刷题后的巩固练习。总结一图理解前缀和的“世界观”把所有变体收敛回一条主线前缀和的核心脉络是定义sum[i]记录从起点到位置i的累计值和/乘/异或均可容斥区间[i, j]的结果 f(prefix(j)) ⊖ f(prefix(i - 1))其中⊖对加法是减法、对乘法是除法、对异或是异或下标偏移前缀和数组从 1 开始原数组从 0 开始查询时先 1 再套模板组合拳与哈希表组合解决“计数 / 最长 / 是否存在”问题与二分组合利用单调性与滑动窗口组合处理“最短 / 连续”问题扩展到二维解决矩阵区域和。仓库 Index/前缀和.md 中的 50 道题正是围绕这条主线层层展开的训练序列而 LeetCode/ 目录下每一篇题解都附有 Java、C、Python、TypeScript 四种语言的完整可运行代码。建议读者先吃透本文的 303、304 两套模板再按索引表难度递进刷题最后用 53、560、209、1310 四道题检验自己对“滚动优化、哈希表、二分、异或”四种变体的掌握程度。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐Windows 和 Office 激活脚本 MAS四种方式怎么选、一行命令怎么跑Windows 和 Office 激活脚本 MAS四种方式怎么选、一行命令怎么跑 MASMicrosoft Activation Scripts是一款开源操作系统LogicStack-LeetCode 树状数组专题从区间求和到多维偏序的完整题解指南LogicStack LeetCode 树状数组专题从区间求和到多维偏序的完整题解指南 导读 本指南以《LogicStack LeetCode宫水三叶的刷题教程文档raylib 环境一次跑通从装库到窗口弹出的最短路径与排错手册raylib 环境一次跑通从装库到窗口弹出的最短路径与排错手册 raylib 是一个用 C 语言写的游戏开发库窗口、2D/3D 图形、纹理、模型、音频这些底游戏开发图形学3D渲染上一篇Brain operations下一篇Fleet 终端用户认证End User AuthenticationmacOS 设置流程中的 IdP 身份集成机制详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LogicStack-LeetCode 前缀和专题实战：从一维区间求和到二维矩阵、异或与哈希变种
教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载LogicStack-LeetCode是公众号「宫水三叶的刷题日记」的刷穿 LeetCode 系列题解仓库其 Index/前缀和.md 是一份覆盖 50 道 LeetCode 题目的「前缀和」专题索引表横跨简单、中等、困难三个难度档位。本文以该索引表为骨架逐类拆解前缀和的核心原理、通用模板并从仓库 LeetCode/ 目录中选取最具代表性的题解源码深入讲解「一维前缀和」「二维前缀和」「前缀和 哈希表」「前缀异或」「前缀和 二分」等实战套路让读者既看得懂公式也拿得到可以直接运行的多语言模板。前缀和是什么从「暴力求和」到「O(1) 区间查询」在 303. 区域和检索 - 数组不可变 与 53. 最大子数组和 两篇题解中仓库给出了前缀和的统一定义所谓前缀和是指对原数组“累计和”的描述通常是指一个与原数组等长的数组。设前缀和数组为sumsum的每一位记录的是从「起始位置」到「当前位置」的元素和。例如sum[x]是指原数组中“起始位置”到“位置x”这一连续段的元素和。有了前缀和数组sum求连续段[i, j]的区域和时利用「容斥原理」即可快速求解通用公式为ans sum[j] - sum[i - 1]之所以要求连续段区域和时“要很自然想到前缀和”是因为它把原本每次O(len)的区间求和变成了预处理一次、之后每次O(1)的查询本质上是“用预处理空间换查询时间”的典型交换。下标偏移从 0 开始的原数组与从 1 开始的前缀和仓库题解中反复强调一个实现细节由于公式涉及i - 1操作为减少边界处理让前缀和数组下标从 1 开始查询时再根据原数组下标是否从 1 开始决定是否进行下标偏移。以 303. 区域和检索 - 数组不可变 的 Java 实现为例class NumArray { int[] sum; public NumArray(int[] nums) { int n nums.length; // 前缀和数组下标从 1 开始因此设定长度为 n 1模板部分 sum new int[n 1]; // 预处理前缀和数组模板部分 for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; } public int sumRange(int i, int j) { // 求某一段区域和 [i, j] 的模板是 sum[j] - sum[i - 1]模板部分 // 但由于源数组下标从 0 开始因此要在模板的基础上进行 1 i; j; return sum[j] - sum[i - 1]; } }仓库原文特意用「模板部分」标注了两处最值得记忆的骨架代码预处理时sum[i] sum[i - 1] nums[i - 1]查询时先i; j再return sum[j] - sum[i - 1]。只要记住这两行一维前缀和的绝大多数裸题都能直接套用。一维前缀和模板多语言仓库在 303. 区域和检索 - 数组不可变 中整理了一维前缀和的最小模板Java 为例// 预处理前缀和数组 { sum new int[n 1]; for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; } // 计算 [i, j] 结果 { i; j; ans sum[j] - sum[i - 1]; }同一份模板在仓库中给出了 Java、C、Python、TypeScript 四种实现写法完全对齐方便在任意语言环境下直接对照移植。模板的底层本质容斥与 DP该模板之所以正确底层依据有二仓库 303 题解 的「总结」一节有明确说明数学/容斥视角某一段的区间和 起点到区间右端点的和含右端点− 起点到区间左端点的和不含左端点DP 视角前缀和的每一位都依赖「前一位置的前缀和」与「当前位置的原数组值」求解过程类似 509. 斐波那契数 的递推属于最朴素的线性 DP。前缀和的第一个变体一维滚动优化求最大子数组和53最大子数组和 是索引表中推荐指数达 的经典题Tag 为「前缀和 / 区间求和问题 / 线性 DP / 分治」。仓库给出的核心思路是先用nums预处理出前缀和数组sum然后在遍历子数组右端点j的过程中通过变量m动态记录已访问的左端点i的前缀和最小值最终在所有sum[j] - m的取值中选取最大值作为答案。代码实现上无需显式构造sum数组直接用变量s表示当前累计前缀和右端点用m记录已访问前缀和的最小值左端点class Solution { public int maxSubArray(int[] nums) { int s 0, m 0, ans -10010; for (int x : nums) { s x; ans Math.max(ans, s - m); m Math.min(m, s); } return ans; } }时间复杂度O(n)、空间复杂度O(1)。仓库同时指出这道题除了「前缀和裸题 有限变量空间优化」的角度还能以线性 DP理解定义f[i]为考虑前i个元素且第nums[i]必选时形成的最大子数组和转移方程为f[i] max(f[i - 1] nums[i], nums[i])由于f[i]只依赖f[i - 1]同样可用有限变量优化写出的代码与前缀和角度几乎一致——两种视角殊途同归是理解前缀和与 DP 关系的最佳样本。进阶分治解法仓库还给出了本题的分治解法Tag 同样包含「分治」递归函数签名设计为int[] dfs(int[] nums, int l, int r)返回值是四元组[sum, lm, rm, max]分别代表「区间和、前缀最大值、后缀最大值、最大子数组和」。合并规则仓库原文待合并信息合并公式区间和sumsum left[0] right[0]前缀最大值lmlm max(left[1], left[0] right[1])后缀最大值rmrm max(right[2], right[0] left[2])最大子数组和maxmax max(left[3], right[3], left[2] right[1])一个需要特别处理的细节lm、rm、max在计算时允许空数组因此当nums全为负数时分治会错误得出最大子数组和为0的答案。仓库的做法是遍历一遍nums若最大值为负数则直接返回该最大值。分治版时间复杂度O(n)、空间复杂度O(log n)。前缀和 哈希表统计和为 K 的子数组个数560和为 K 的子数组 是推荐指数 的前缀和经典题Tag 为「前缀和 / 哈希表」。核心思路仓库原文统计以每一个nums[i]为结尾、和为k的子数组数量即是答案。预处理前缀和数组sum下标从 1 开始后对以nums[i]结尾的区间本质是求在[0, i]中sum数组里有多少个值为sum[i 1] - k的数——这可以在遍历过程中用「哈希表」同步记录每个前缀和值出现的次数class Solution { public int subarraySum(int[] nums, int k) { int n nums.length, ans 0; int[] sum new int[n 10]; for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; MapInteger, Integer map new HashMap(); map.put(0, 1); // 前缀和为 0 出现过一次对应「空子数组」 for (int i 1; i n; i) { int t sum[i], d t - k; ans map.getOrDefault(d, 0); map.put(t, map.getOrDefault(t, 0) 1); } return ans; } }注意map.put(0, 1)这一行它代表“前缀和为 0 在位置 0 出现过一次”用于正确统计「从下标 0 开始的子数组」是哈希表变体中容易遗漏的初始化。时间复杂度O(n)、空间复杂度O(n)。前缀和的哨兵技巧寻找数组的中心下标724寻找数组的中心下标 是一道前缀和裸题仓库给出了三档空间优化非常适合用来演示前缀和的不同写法写法一前后两遍前缀和 哨兵。为简化数组越界判断前缀和数组多预留一位作为哨兵本题需要前后两个方向的前缀和因此直接多开两位class Solution { public int pivotIndex(int[] nums) { int n nums.length; int[] s1 new int[n 2], s2 new int[n 2]; for (int i 1; i n; i) s1[i] s1[i - 1] nums[i - 1]; for (int i n; i 1; i--) s2[i] s2[i 1] nums[i - 1]; for (int i 1; i n; i) { if (s1[i] s2[i]) return i - 1; } return -1; } }写法二一遍前缀和。只处理一遍前缀和判定某个下标是否为“中心下标”时用前缀和现场计算左侧值与右侧值left sum[i - 1]right sum[n] - sum[i]。仓库指出这只是常数级别的优化不改变时空复杂度。写法三优化至 O(1) 空间。先求一遍总和total再用sum记录当前遍历位置的左侧总和中心下标必然满足sum total - sum - nums[i]左边值 右边值无需任何额外数组class Solution { public int pivotIndex(int[] nums) { int n nums.length, total 0, sum 0; for (int i 0; i n; i) total nums[i]; for (int i 0; i n; i) { if (sum total - sum - nums[i]) return i; sum nums[i]; } return -1; } }前缀和的容斥变体除自身以外数组的乘积238除自身以外数组的乘积 的 Tag 是「前缀和 / 容斥原理」但它实际用的是前缀乘与后缀乘——这是“前缀和思想”在乘法语境下的直接迁移。对每个ans[i]其值由两部分组成(nums[0] × nums[1] × ... × nums[i - 1]) × (nums[i 1] × nums[i 2] × ... × nums[n - 1])因此用s1记录范围[1, x]的前缀乘s2记录范围[x, n]的后缀乘然后ans[i - 1] s1[i - 1] × s2[i 1]。仓库还给出了空间优化版直接复用ans数组先从左到右累乘前缀部分再从右到左累乘后缀部分最终空间复杂度降为O(1)输出数组不计入额外空间。这道题与 53 题 一起说明了前缀和的“可迁移性”只要某个答案能拆成“前缀部分 × 后缀部分”或和/差/异或前缀和思想就能以 O(1) 查询的代价解决它。二维前缀和矩阵区域求和与容斥公式304二维区域和检索 - 矩阵不可变 是「二维前缀和」裸题推荐指数 。仓库给出了清晰的定义二维前缀和数组中的每一个格子记录的是「以当前位置为区域的右下角区域左上角恒定为原数组的左上角的区域和」。预处理公式sum[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i - 1][j - 1] matrix[i - 1][j - 1]查询左上角(x1, y1)、右下角(x2, y2)的区域和公式容斥sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] sum[x1 - 1][y1 - 1]完整 Java 实现仓库原文class NumMatrix { int[][] sum; public NumMatrix(int[][] matrix) { int n matrix.length, m n 0 ? 0 : matrix[0].length; // 与「一维前缀和」一样前缀和数组下标从 1 开始模板部分 sum new int[n 1][m 1]; // 预处理前缀和数组模板部分 for (int i 1; i n; i) { for (int j 1; j m; j) { sum[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i - 1][j - 1] matrix[i - 1][j - 1]; } } } public int sumRegion(int x1, int y1, int x2, int y2) { // 求区域和模板sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] sum[x1 - 1][y1 - 1]模板部分 // 由于源数组下标从 0 开始先全部 1 x1; y1; x2; y2; return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] sum[x1 - 1][y1 - 1]; } }时间复杂度预处理O(n * m)单次查询O(1)空间复杂度O(n * m)。二维前缀和模板记忆法仓库在 304 题解 中分享了一套口诀式的记忆法预处理当前格子(和) 上方的格子(和) 左边的格子(和) − 左上角的格子(和) 当前格子(值)查询先把原数组坐标全部 1 转为前缀和坐标然后记作22 − 12 − 21 11即sum[x2][y2]减去x1-1行、y1-1列再加回减重的左上角(x1-1, y1-1)。二维前缀和的延伸题索引表中与二维前缀和强相关的题目还有最大矩形在二维前缀和/单调栈基础上求解最大全 1 矩形元素和为目标值的子矩阵数量枚举矩阵上下边界后用一维前缀和 哈希表统计矩形区域不超过 K 的最大数值和二维前缀和结合有序集合优化枚举找出第 K 大的异或坐标值二维异或前缀和 排序/堆。前缀异或把容斥从减法换成异或1310子数组异或查询 展示了前缀和思想在“异或”语境下的迁移Tag 为「数学 / 树状数组 / 前缀和」。仓库的核心结论xor(l, r) xor(1, r) ⊕ xor(1, l - 1)本质上还是利用集合区间结果的容斥原理。只不过前缀和需要利用「减法逆运算」做容斥而前缀异或是利用「相同数值进行异或结果为 0偶数次的异或结果为 0」的特性实现容斥。前缀异或实现class Solution { public int[] xorQueries(int[] arr, int[][] qs) { int n arr.length, m qs.length; int[] sum new int[n 1]; for (int i 1; i n; i) sum[i] sum[i - 1] ^ arr[i - 1]; int[] ans new int[m]; for (int i 0; i m; i) { int l qs[i][0] 1, r qs[i][1] 1; ans[i] sum[r] ^ sum[l - 1]; } return ans; } }时间复杂度O(n m)、空间复杂度O(n)。仓库还顺带对比了「树状数组」与「前缀异或」本题不涉及修改操作因此无需树状数组前缀异或即可把查询复杂度从O(log n)降到O(1)。此外仓库在本题中总结了“区间求值问题”的方案选型表极具实战价值场景可选方案数组不变求区间和前缀和、树状数组、线段树多次修改某个数求区间和树状数组、线段树多次整体修改某个区间求区间和线段树、树状数组视修改区间数据范围而定多次将某个区间变成同一个数求区间和线段树、树状数组结论线段树能解决的问题最多但代码长、常数大只有在不得不用时才考虑。索引表中的异或前缀和相关题目还包括 1442. 形成两个异或相等数组的三元组数目异或前缀和 枚举、1738. 找出第 K 大的异或坐标值二维异或前缀和。前缀和 二分利用单调性把 O(n²) 降为 O(n log n)209长度最小的子数组 的 Tag 为「前缀和 / 二分 / 滑动窗口」。因为nums[i]的取值范围是[1, 10^5]全为正数前缀和数组天然满足单调递增具备二段性可以二分。核心思路仓库原文对每个nums[i]视作子数组右端点其前缀和值为s sum[i 1]问题转换为在前缀和数组下标[0, i]范围内找到满足「值小于等于s - t」的最大下标充当子数组左端点的前一个位置。二分采用“找右边界”写法l mid 1分支在sum[mid] d时成立class Solution { public int minSubArrayLen(int t, int[] nums) { int n nums.length, ans n 10; int[] sum new int[n 10]; for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; for (int i 1; i n; i) { int d sum[i] - t; int l 0, r i; while (l r) { int mid l r 1 1; if (sum[mid] d) l mid; else r mid - 1; } if (sum[r] d) ans Math.min(ans, i - r); } return ans n 10 ? 0 : ans; } }时间复杂度O(n log n)、空间复杂度O(n)。仓库同时给出滑动窗口解法复杂度可降到O(n)、空间O(1)——两种解法并存正好演示“前缀和擅长利用单调性做二分滑动窗口则直接在原数组上维护窗口和”。前缀和的多场景组合索引表全景导读回到 Index/前缀和.md 这份索引表本身50 道题几乎覆盖了前缀和的所有组合形态可按下表快速定位适合自己的练习路线场景 / 组合代表题仓库路径一维前缀和裸题区间求和303、724、1480、1588LeetCode 对应目录前缀和 哈希表计数/最长560、525、930、523、437LeetCode 对应目录前缀和 二分 / 单调性209、1208、1838LeetCode 对应目录二维前缀和容斥304、85、1074、363LeetCode 对应目录前缀异或异或容斥1310、1442、1738LeetCode 对应目录前缀乘容斥变体238LeetCode/231-240前缀和滚动优化有限变量53、396、1749LeetCode 对应目录前缀和 排序 / 双指针327、825、689LeetCode 对应目录前缀和 差分区间增量1094、1109、2055、2100LeetCode 对应目录前缀和 随机 / 权重采样497、528、710LeetCode 对应目录剑指 Offer / LCR 系列剑指 Offer II 008、剑指 Offer II 010、剑指 Offer II 011、LCR 161同 53LeetCode/剑指 Offer II、LeetCode/LCR索引表中其余题目如 187. 重复的DNA序列、926. 将字符串翻转到单调递增、1154. 一年中的第几天 之外的对应目录、629. K个逆序对数组、661. 图片平滑器、1422. 分割字符串的最大得分、1537. 最大得分、1652. 拆炸弹、1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗、1894. 找到需要补充粉笔的学生编号、1004. 最大连续1的个数 III则分别从字符串前缀统计、双指针、枚举等角度复用同一套“累计和 容斥”思想难度档位从简单到困难递进可作为刷题后的巩固练习。总结一图理解前缀和的“世界观”把所有变体收敛回一条主线前缀和的核心脉络是定义sum[i]记录从起点到位置i的累计值和/乘/异或均可容斥区间[i, j]的结果 f(prefix(j)) ⊖ f(prefix(i - 1))其中⊖对加法是减法、对乘法是除法、对异或是异或下标偏移前缀和数组从 1 开始原数组从 0 开始查询时先 1 再套模板组合拳与哈希表组合解决“计数 / 最长 / 是否存在”问题与二分组合利用单调性与滑动窗口组合处理“最短 / 连续”问题扩展到二维解决矩阵区域和。仓库 Index/前缀和.md 中的 50 道题正是围绕这条主线层层展开的训练序列而 LeetCode/ 目录下每一篇题解都附有 Java、C、Python、TypeScript 四种语言的完整可运行代码。建议读者先吃透本文的 303、304 两套模板再按索引表难度递进刷题最后用 53、560、209、1310 四道题检验自己对“滚动优化、哈希表、二分、异或”四种变体的掌握程度。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐Windows 和 Office 激活脚本 MAS四种方式怎么选、一行命令怎么跑Windows 和 Office 激活脚本 MAS四种方式怎么选、一行命令怎么跑 MASMicrosoft Activation Scripts是一款开源操作系统LogicStack-LeetCode 树状数组专题从区间求和到多维偏序的完整题解指南LogicStack LeetCode 树状数组专题从区间求和到多维偏序的完整题解指南 导读 本指南以《LogicStack LeetCode宫水三叶的刷题教程文档raylib 环境一次跑通从装库到窗口弹出的最短路径与排错手册raylib 环境一次跑通从装库到窗口弹出的最短路径与排错手册 raylib 是一个用 C 语言写的游戏开发库窗口、2D/3D 图形、纹理、模型、音频这些底游戏开发图形学3D渲染上一篇Brain operations下一篇Fleet 终端用户认证End User AuthenticationmacOS 设置流程中的 IdP 身份集成机制详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考