参考
1906. 查询差绝对值的最小值 差[l,r]的绝对值最小值。用前缀和判断[l,r]有没有数字num（范围有限 因此利用前缀和可以计算出每个区间的频数，然后遍历范围K就可以拿到是否存在该区间了)
模板
一维前缀和
arr = []
pre = [0]
for i in range(len(arr)):
pre.append(pre[-1] + arr[i])
# 获取[l,r]区间和
def get_pre(l, r):
return pre[r + 1] - pre[l]
二维前缀和
# 初始化
m, n = len(grid), len(grid[0])
pre = [[0] * (n + 1) for _ in range(m + 1)]
# 获取区间[(x,y)到(x1,y1)]的矩形区间和
# x range in [0,m)
def get_pre(x, y, x1, y1):
return pre[x1 + 1][y1 + 1] + pre[x][y] - pre[x1 + 1][y] - pre[x][y1 + 1]
# 前缀和计算
for i in range(m):
for j in range(n):
pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + grid[i][j]
Python模板
class Pre:
def __init__(self, arr):
pre = [0]
for i in range(len(arr)):
pre.append(pre[-1] + arr[i])
self.pre = pre
# 获取[l,r]区间和, 从0开始
def get_pre(self, l, r):
return self.pre[r + 1] - self.pre[l]
class Pre2:
# 根据m*n的grid初始化前缀和
def __init__(self, grid):
# 初始化
m, n = len(grid), len(grid[0])
pre = [[0] * (n + 1) for _ in range(m + 1)]
# 前缀和计算
for i in range(m):
for j in range(n):
pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + grid[i][j]
self.pre = pre
# 获取区间[(x,y)到(x1,y1)]的矩形区间和
# x range in [0,m)
def get_pre(self, x, y, x1, y1):
pre = self.pre
return pre[x1 + 1][y1 + 1] + pre[x][y] - pre[x1 + 1][y] - pre[x][y1 + 1]
$0 基础前缀和
pre的key是index, value是开头到现在的累计value和
| 题目 | 备注 |
|---|---|
| 303. 区域和检索 - 数组不可变 304. 二维区域和检索 - 矩阵不可变 | 前缀和与差分 |
$1 频数前缀和
pre的key是num, pre的value是累计出现次数
| 题目 | 备注 |
|---|---|
| 1177. 构建回文串检测 多次查某个区间构建回文串需要改几个字符 | 题解 |
| 1862. 向下取整数对和 | 题解 |
维护前缀频数前缀状态：prefix_cnts[i + 1] := [0..i] 的字符计数
[l, r] 的字符计数为 prefix_cnts[r + 1] - prefix_cnts[l]
相当于前缀是一个频数的map，这样就可以知道一个区间的各个字符的频率了。
1862. 向下取整数对和 给你一个整数数组 nums ，请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大，请你返回答案对109 + 7 取余 的结果。
解答: 暴力法就是枚举x,y,然后求floor(x/y)，可以倒过来枚举y和d， x的范围是d*y 到(d+1)*y ，求一个范围内的数量可以用前缀和。
class Solution:
def sumOfFlooredPairs(self, nums: List[int]) -> int:
mod = 10**9 + 7
# 元素最大值
upper = max(nums)
cnt = [0] * (upper + 1)
for num in nums:
cnt[num] += 1
# 预处理前缀和
pre = [0] * (upper + 1)
for i in range(1, upper + 1):
pre[i] = pre[i - 1] + cnt[i]
ans = 0
for y in range(1, upper + 1):
# 一个小优化，如果数组中没有 y 可以跳过
if cnt[y]:
d = 1
while d * y <= upper:
ans += cnt[y] * d * (pre[min((d + 1) * y - 1, upper)] - pre[d * y - 1])
d += 1
return ans % mod
$2 数据结构维护前缀和
单调队列维护
| 题目 | 备注 |
|---|---|
| 53. 最大子序和 918. 环形子数组的最大和 | 题解 |
918. 环形子数组的最大和 给定一个由整数数组 A 表示的环形数组 C，求 **C** 的非空子数组的最大可能和。
其实就是分两种情况，一种是中间最大值，一种是两端点各有一段。
单调栈维护
| 题目 | 备注 |
|---|---|
| 1124. 表现良好的最长时间段 | 题解 |
# 前缀和
presum = [0] * (n + 1)
for i in range(1, n + 1):
presum[i] = presum[i - 1] + score[i - 1]
ans = 0
stack = []
# 顺序生成单调栈，栈中元素从第一个元素开始严格单调递减，最后一个元素肯定是数组中的最小元素所在位置
for i in range(n + 1):
if not stack or presum[stack[-1]] > presum[i]:
stack.append(i)
# 倒序扫描数组，求最大长度坡
i = n
while i > ans:
while stack and presum[stack[-1]] < presum[i]:
ans = max(ans, i - stack[-1])
stack.pop()
i -= 1
HashMap 维护
(1) 键是前缀和的值，值为第一次出现时的索引
| 题目 | 备注 |
|---|---|
| 325. 和等于 k 的最长子数组长度 | 题解 |
| 525. 连续数组 | 频数前缀和, 记录 1 和 0 的个数差 |
| 1371. 每个元音包含偶数次的最长子字符串 | 题解 |
| 1542. 找出最长的超赞子字符串 | 频数前缀和，记录 0,1,2,3,4,5,6,7,8,9 的个数的奇偶性 |
(2) 键是前缀和的值，值为出现次数
| 题目 | 备注 |
|---|---|
| 560. 和为K的子数组 | 1074. 元素和为目标值的子矩阵数量 的一维版本, 题解 |
| 1248. 统计优美子数组 | 题解 |
560. 和为K的子数组 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
解答： 记录前缀和，利用hash表存储sum 到 count的数量，遍历时累加。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int sum = 0, res = 0;
unordered_map<int, int> map1;
map1[0] = 1;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (map1.count(sum - k)) {
res += map1.at(sum - k);
}
map1[sum]++;
}
return res;
}
};
(3) 键是前缀和模 K 的余数
| 题目 | 备注 |
|---|---|
| 523. 连续的子数组和 | 值为第一次出现时的索引 |
| 974. 和可被 K 整除的子数组 | 值为出现次数 |
| 1590. 使数组和能被 P 整除 | 值为最后一次出现时的索引 |
| 1524. 和为奇数的子数组数目 | 值为出现次数 |
523. 连续的子数组和 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：子数组大小 至少为 2 ，且子数组元素总和为 k 的倍数。
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
s = set()
pre = [0 for _ in range(len(nums) + 1)]
for i in range(len(nums)):
pre[i + 1] = pre[i] + nums[i]
for i in range(1, len(nums)):
s.add(pre[i - 1] % k)
if (pre[i+1] % k) in s:
return True
return False
leetcode 974 和可被 K 整除的子数组， 给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
class Solution {
public int subarraysDivByK(int[] A, int K) {
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int presum = 0;
int count = 0;
for (int x : A) {
presum += x;
//当前 presum 与 K的关系，余数是几，当被除数为负数时取模结果为负数，需要纠正
int key = (presum % K + K) % K;
//查询哈希表获取之前key也就是余数的次数
if (map.containsKey(key)) {
count += map.get(key);
}
//存入哈希表当前key，也就是余数
map.put(key,map.getOrDefault(key,0)+1);
}
return count;
}
}
$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. 字符串的好分割数目 | 频数前缀和, 统计字符的个数 |
$6 前缀和预处理优化 dp
- 用前缀和预处理原始数组
| 题目 | 备注 |
|---|---|
| 837. 新21点 | - |
| 1444. 切披萨的方案数 | - |
| 1478. 安排邮筒 | - |
$7 前缀和优化 dp
- 用前缀和维护 dp 数组
| 题目 | 备注 |
|---|---|
| 1871. 跳跃游戏 VII | 题解 |
$8 差分
| 题目 | 备注 |
|---|---|
| 56. 合并区间 | 题解, 更好的做法是排序后贪心或者扫描线 |
| 370. 区间加法 | 题解, 用差分维护区间加法模板 |
| 1109. 航班预订统计 | 题解 |
$9 其它
| 题目 | 备注 |
|---|---|
| 1381. 设计一个支持增量操作的栈 | 题解 |
| 689. 三个无重叠子数组的最大和 | 在预处理出的序列上再做前缀和 |