前缀和

发表于： 分类于：
字数： 1542 阅读：≈ 4分钟

前缀和题单

一维前缀和

LC 1749

任意子数组和的绝对值的最大值: 在前缀和数组里面找最小值和最大值，他们的差的绝对值就是答案。

1
2
3

def maxAbsoluteSum(self, nums: List[int]) -> int:
    s = list(accumulate(nums, initial=0))  # nums 的前缀和
    return max(s) - min(s)

2055. 蜡烛之间的盘子

  1. 找a或其右边第一个蜡烛
  2. 找b或其左边第一个蜡烛
  3. 用前缀和，算他们之间的盘子数量

步骤1，2可以用二分，但是会超时
最好是预处理，记录每个位置左边/右边的第一个蜡烛位置

前缀和与哈希表

枚举右，维护左. 关键找出【维护左】的性质！

1524. 和为奇数的子数组数目

利用性质:odd-even=odd, even-odd=odd

2845. 统计趣味子数组的数目

涉及到模。模运算对加减法封闭！

LC 560

输入：nums = [1,2,3], k = 3 输出：2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def subarraySum(self, nums: List[int], k: int) -> int:
    res=0
    n=len(nums)
    s=[0]*(n+1)
    for i, x in enumerate(nums):
        s[i+1]=s[i]+x
    cnt=defaultdict(int)
    for sj in s:
        res+=cnt[sj-k]
        cnt[sj]+=1
    return res

3026. Maximum Good Subarray Sum

好数组：第一个数字和最后一个数字的差的绝对值为 1。

定义哈希表minS, key为数组中的元素x，value为所有x所在的位置的前缀和最小值(不包括x本身)

1124. Longest Well-Performing Interval

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
输入：hours = [9,9,6,0,6,6,9] 输出：3 解释：最长的表现良好时间段是 [9,9,6]。

3381. 长度可被 K 整除的子数组的最大元素和

返回 nums 中一个 非空子数组 的 最大 和，要求该子数组的长度可以 被 k 整除。

模运算

2488

中位数，转换为+1，-1的逻辑

距离和

1685. 有序数组中差绝对值之和

Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]

距离和做法：遍历到 nums[i]=x, 它与左边数的差之和为 xi-preSum[i]；它与右边数的差之和为 preSum[-1]-preSum[i+1]-x(n-i-1)

也可以用动归做：设 s=nums[i]到其它数的距离和，设nums[i+1]=nums[i]+d,

那么 nums[i+1]到其它数的距离和为s+id-(n-i-2)d=s+d(2i+2-n)

异或

1310. 子数组异或查询

异或的结合律

1177. 构建回文串检测

如何快速求出子串中每种字母的个数？奇偶性联想到异或。
1^1=0, 0^1=1, 因此与1进行异或可以改变奇偶

幂的前缀和

2438. 二的幂数组中查询范围内的乘积

二维前缀和 

1
2
3
4
5

m,n=len(matrix), len(matrix[0])
p=[[0]*(n+1) for _ in range(m+1)]
for i in range(m):
    for j in range(n):
        p[i+1][j+1]=p[i][j+1]+p[i+1][j]-p[i][j]+int(matrix[i][j])

221. 最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

考虑优化:

  1. 枚举每一个坐标，将其作为矩形左上角；再枚举边长。
  2. 如果对于一个坐标，它拥有边长为x的最大正方形，那么对于下一个坐标，边长的枚举从 x+1 开始
  3. 如果对于一个坐标，边长为 y 时，矩形并不是全 1 的，那么直接 break，进入到下一个坐标。

动态规划:
dp[i][j]记录以i,j为右下角的valid正方形最大边长。如果该位置的值是 1，则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1

差分数组

给 num[i]到num[j]各增加x,相当于给差分数组diff[i]增加x, diff[j+1]减少x

1
2
3
4
5
6

diff=[0]*(n+1)
tooAdd=[0]*(n+1)
#遍历某个list，把所有要加的区间合并加到toAdd
toAdd=list(accumulate(diff))
for i in range(n):
    nums[i]+=toAdd[i]

原地还原数组：

1
2

for i in range(n):
    diff[i+1]+=diff[i]

差分数组性质：
如果一个数组全为正数，那么差分数组的任意前缀和为正。

1526🌟

贪心,逆向求最少操作数
套路：

  1. 求从 initial 到 target 的ops 数组
  2. 为ops数组求 diff
  3. 贪心地观察 diff
1
2
3
4
5

diff=[0]*(n+1)
pre=0
for i in range(n):
    diff[i]=target[i]-pre
    pre=target[i]

diff的最后一位视作“黑洞”

所以diff中的负数，一定需要被前面的正数“吸收”。那么就是负数的绝对值大小之和，加上正数之和+负数

类似的异或贪心问题：995

2015. 每段建筑物的平均高度🌟

扫描线。为了减少空间，需要使用哈希表

二维差分

初始化

1

diff==[[0]*(n+2) for _ in range(m+2)]

2536. 子矩阵元素加 1🌟 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

diff=[[0]*(n+2) for _ in range(n+2)]
#左上角为[a,b],右下角为[c,d]的矩形，每个格子加一
diff[a+1][b+1]+=1
diff[a+1][d+2]-=1
diff[c+2][b+1]-=1
diff[c+2][d+2]+=1

#得到前缀和数组
for i in range(n):
    for j in range(n):
        diff[i+1][j+1]+=diff[i][j+1]+diff[i+1][j]-diff[i][j]
#此时答案四周包裹了无用的数

2132. 用邮票贴满网格图🌟

二维前缀和+二维差分