前缀和问题分类汇总

  |  

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

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


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

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


$0 基础前缀和

$1 频数前缀和

$2 数据结构维护前缀和

单调队列维护

单调栈维护

HashMap 维护

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

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

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

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

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

$3 二维前缀和

$4 运算推广

前缀积

前缀异或

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

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

$6 前缀和预处理优化 dp

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

$7 前缀和优化 dp

  • 用前缀和维护 dp 数组

$8 差分

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

$9 其它


Share