前缀和 - wenzhoullq/leetcode GitHub Wiki
连续
先构建前缀和数组
int len=nums.length;
int[] sum=new int[len+1];
for(int i=1;i<=len;i++){
sum[i]=sum[i-1]+nums[i-1];
}思考这么两个问题
- 问题 1
为什么sum数组取的是len+1?
前缀和的目的是为了能够O(1)的方式计算某一段连续子序列的和，如果我想O(1)计算[i,j]之间的和,注意这里的i和j指的是arr[]的,那么即sum[j+1]-sum[i]
而如果我想计算从0个开始的子数组之和，必须引入一个sum[0],这样就保证任意子数组之和的公式都是sum[i]-sum[j],归根到底,sum[0]是哨兵
- 问题 2
前缀和数组构造需求有几种？
- 最简单求和的前缀和数组
for (int i = 1; i <= len; i++) sum[i] = sum[i - 1] + nums[i - 1];- 一段子序列中变量的个数前缀和数组
for (int i = 1; i <= len; i++) sum[i] = sum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);3.一段子序列的和为k的倍数
for(int i=1;i<=len;i++) sum[i]=((sum[i-1]+nums[i-1])%k+k)%k;4.字段子序列的和的余数是mod
for(int i=1;i<=nums.length;i++){
long temp=(sum[i]-mod)%p;//与上面的处理不同的是，余数的处理是在这里处理的
if(m.containsKey(temp)) ans=Math.min(i-m.get(temp),ans);
m.put(sum[i]%p,i);
}
5.dfs前缀和数组
int dfs(TreeNode root){
list.add(root.val);
dfs(root.left);
dfs(root.right);
list.removeLast();
}6.重复子序列
for(int i=1;i<=n;i++){
sum1[i]=sum1[i-1]+(s[i-1]==strs[i%3]?0:1);//注意这个括号，比较重要
sum2[i]=sum2[i-1]+(s[i-1]==strs[(i+1)%3]?0:1);
sum3[i]=sum3[i-1]+(s[i-1]==strs[(i+2)%3]?0:1);
}在构建好前缀和数组后，对前缀和数组进行使用，对前缀和数组的使用方式有两种
- 非map/非精准求值
for(int i=1;i<=len;i++){
for(int j=0;j<i;j++){
if( pre[i]-pre[j] 满足条件) //处理
}
}容易分析到，时间复杂度为O(n²),但是一些长度较长的，如length<=1e6,显然会超时，我们必须得使用O(n)来做题
既然和计算能拿来做，异或计算也可以拿来做
- hashmap/hashSet/精准求值
使用hashmap有两种需求，一种是对长度的需求（最大长度），另一种是对数量的需求（最大数量）,hashset适用于求不交叉的子数组个数
- 最大长度
- hashmap
Map<Integer, Integer> m = new HashMap<>();
m.put(sum[0],0);//哨兵
for (int i = 1; i <= len; i++) {
if(m.containsKey(sum[i])) ans=Math.max(ans,i-m.get(sum[i]));
else m.put(sum[i],i);//如果是最短长度，那么else忽略
}- 最大数量
- hashmap
HashMap<Integer,Integer> m=new HashMap<>();
m.put(sum[0],1);//哨兵，注意两种不同的哨兵建立方式
for(int i=1;i<=len;i++){
ans+=m.getOrDefault(sum[i]-k,0);
m.put(sum[i],m.getOrDefault(sum[i],0)+1);
}- hashset
HashSet<Integer> s=new HashSet<>();
s.add(0);//哨兵
int ans=0;
for(int i=1;i<=nums.length;i++){
if(s.contains(sum[i]-target)) {
s.clear();//清除是关键
ans++;
s.add(sum[i]);
continue;
}
s.add(sum[i]);
}
return ans;
}
}容易分析的是，hashmap的方式是O(n),与暴力相比快太多，是不是意味着非map的方式无用？
并非如此，hashmap是精准求值，而暴力的方式可以对不精准的目标，如某子序列之和>某值特别适用；如果暴力超时的话，应该存在别的优化方式
396. 旋转函数 如果是旋转类的前缀和，可以将写一个两倍长的sum[]来替代前找的动作
437. 路径总和 III (dfs前缀和)
974. 和可被 K 整除的子数组 余数，但是余数中出现负数，还要对负数处理（+k）
C. Yet Another Walking Robot-灵茶2023.4.12
862. 和至少为 K 的最短子数组 这题暴力会超时，使用的是滑动窗口，但是滑动窗口的前提是单调，于是用单调队列维持单调
- hashmap
- hashset
多重for循环往往是针对前缀和段排列顺序有要求/多个前缀和段
1749. 任意子数组和的绝对值的最大值 (求连续和的最大值有贪心的解法，同时这题是多重for循环的前缀和，但是可以通过优化的方式把O(n²)降低到O(1))
1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？ 关键点：只有干完XXX才能后续步骤，前缀和思想，用除的方式优于乘
表面上不是前缀和，但是转换后成为前缀和
2106. 摘水果 表面上不是前缀和，但是左右移动可以完全成（左2+右/右2+左）
前缀和+二分与二分+前缀和不同，一个是前缀和为导向，对前缀和查找需要二分；另一个是二分为导向，对前缀和
528. 按权重随机选择 权重用前缀和来处理
2055. 蜡烛之间的盘子 值得注意的是二分求最接近的下标
以二分为切入点，前缀和辅助
1124. 表现良好的最长时间段 这里是后者大于前者的最大宽度单调栈模板
1856. 子数组最小乘积的最大值这个是类似于求最大矩阵面积的单调栈模板
前缀和的状态压缩有两种题型，第一种题型是该区间的奇偶个数，使用^运算;另一种是该区间的存在型，使用|运算，通常|运算伴随着去重 如果问存在一个奇数(为什么是奇数，因为为0的话可能是偶数出现也可能是0次出现)，需要对前面存的情况的某一位^1
for(int j = 0 ; j < 10; j++){
int t = temp^(1<<j);
if(m.containsKey(t))ans =Math.max(ans,);
}
- 奇偶个数
1915. 最美子字符串的数目 题目说只涉及到前10个字母，因此需要联想到状态压缩
- 存在性
2017. 网格游戏 自己最大并非别人最小，别人最小才是目的
和arr[][]下标比大1 O(1)时间求面积,可以用于O(1)的查询某个区域内有无标志
//初始化
int leny=,lenx=;
int[][] sum=new int[leny+1][lenx+1];
for(int i = 1; i <= leny;i++)
for(int j = 1; j<=lenx ;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+martix[i-1][j-1]; int x1+1,y1+1,x2+1,y2+1;//x1,y1是左上角的坐标+1，x2,y2是右下角的坐标+1
area=sum[y2][x2]-sum[y1-1][x2]-sum[y2][x1-1]+sum[y1-1][x1-1];
不仅仅是求和，求^的二维矩阵也可以使用
int leny=xxx,lenx=xxx;
int[][] sum=new int[leny][lenx];
sum[i][j]=sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]^martix[i-1][j-1];
area=sum[y2][x2]^sum[y1-1][x2]^sum[y2][x1-1]^sum[y1-1][x1-1];661. 图片平滑器 (值得注意点的是，这个是以固定长度的矩阵去横扫，并且边界上也会横扫，那么会出现越界问题，如何处理越界呢，用Math.max(0,i-1);
2132. 用邮票贴满网格图O(1)求标志位
子数组往往用到前缀和，但是需要等价转换