前缀和问题分类汇总

摘要: 本文系统梳理了前缀和的算法要点。并汇总了 leetcode 上的相关的题目。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文总结了力扣上 2000 题以内的关于前缀和的 44 道题，思路接近的题放到了一起。

刷完这份题目列表，力扣范围内的前缀和问题可以说刷爆了。

---

$0 基础前缀和

题目	备注
303. 区域和检索 - 数组不可变 304. 二维区域和检索 - 矩阵不可变	前缀和与差分

$1 频数前缀和

题目	备注
1177. 构建回文串检测	题解
1862. 向下取整数对和	题解

$2 数据结构维护前缀和

单调队列维护

题目	备注
53. 最大子序和 918. 环形子数组的最大和	题解

单调栈维护

题目	备注
1124. 表现良好的最长时间段	题解

HashMap 维护

(1) 键是前缀和的值，值为第一次出现时的索引

题目	备注
325. 和等于 k 的最长子数组长度	题解
525. 连续数组	频数前缀和, 记录 1 和 0 的个数差
1371. 每个元音包含偶数次的最长子字符串	题解
1542. 找出最长的超赞子字符串	频数前缀和，记录 0,1,2,3,4,5,6,7,8,9 的个数的奇偶性

(2) 键是前缀和的值，值为出现次数

题目	备注
560. 和为K的子数组	【1074. 元素和为目标值的子矩阵数量 】的一维版本, 在数据结构中维护前缀和：区间(矩形/路径)和等于(大于)目标值
1248. 统计优美子数组	题解

(3) 键是前缀和模 K 的余数

题目	备注
523. 连续的子数组和	值为第一次出现时的索引
974. 和可被 K 整除的子数组	值为出现次数
1590. 使数组和能被 P 整除	值为最后一次出现时的索引
1524. 和为奇数的子数组数目	值为出现次数

$3 二维前缀和

题目	备注
1074. 元素和为目标值的子矩阵数量	【560. 和为K的子数组】 的二维版本, 题解
面试题 17.24. 最大子矩阵	思路类似于 【53. 最大子序和】, 题解
363. 矩形区域不超过 K 的最大数值和	在【面试题 17.24. 最大子矩阵】基础上加了一个 K, 题解
1292. 元素和小于等于阈值的正方形的最大边长	二分 + 二维前缀和
1314. 矩阵区域和	-
1139. 最大的以 1 为边界的正方形	用两组一维前缀和

$4 运算推广

前缀积

题目	备注
152. 乘积最大子数组	题解
1352. 最后 K 个数的乘积	题解

前缀异或

题目	备注
1310. 子数组异或查询	基础前缀异或
1442. 形成两个异或相等数组的三元组数目	哈希表维护前缀异或结果
1738. 找出第 K 大的异或坐标值	二维前缀异或

$5 同时需要前缀和与后缀和信息

题目	备注
238. 除自身以外数组的乘积	-
724. 寻找数组的中心索引	-
1477. 找两个和为目标值且不重叠的子数组	-
926. 将字符串翻转到单调递增	-
838. 推多米诺	-
828. 统计子串中的唯一字符	题解
1525. 字符串的好分割数目	频数前缀和, 统计字符的个数
2100. 适合打劫银行的日子	-

$6 前缀和预处理优化 dp

• 用前缀和预处理原始数组

题目	备注
837. 新21点	-
1444. 切披萨的方案数	-
1478. 安排邮筒	题解

$7 前缀和优化 dp

• 用前缀和维护 dp 数组

题目	备注
1871. 跳跃游戏 VII	题解

$8 差分

题目	备注
56. 合并区间	题解, 更好的做法是排序后贪心或者扫描线
370. 区间加法 1109. 航班预订统计	题解, 用差分维护区间加法模板

$9 其它

题目	备注
1381. 设计一个支持增量操作的栈	题解
689. 三个无重叠子数组的最大和	题解

---