前缀和

数组nums的某一段子区间和,前n项和数组。

数组中子区间和等于k的最长长度。用unordered_map记录某个前n项和值第一次出现的位置,注意m[0]=-1,第一项之前的前n项和为0,索引为-1,比如nums=[1,2],k=3,则m[0]=-1,m[1]=0,m[3]=1,m[3-3]存在,其值为-1,则len=1-(-1)=2,子区间最长为2,遍历nums,如果m中没有前n项和,记录该前n项和第一次出现的位置m[sum]=i,如果m[k-sum]存在,说明从m[k-sum]到i的nums范围的和是k,比较区间长度,找到最大值。
0,1字符串中最长包含相同0和1数量的子字符串长度。同上题,采用前缀和和哈希表的方法,统计1和0出现的次数,遇到1cnt+++,遇到0cnt--,初始位置cnt的值为0,索引为-1,记录初次遇到的cnt值所在的索引,当后面再次遇到该cnt值,说明从初次遇到的位置到目前的位置形成的子字符串里0和1的数量相等。为什么要为哈希表添加键值对{0,-1},因为我们定义前缀和数组prefix,一般认为初始情况,前0项和prefix[0]=0,而prefix的大小是n+1,这样算到前n项和,子区间和就前n项和的差,这两个问题里我们计算前n项和的索引是n-1,则初始情况线性平移设置0对应的索引是-1

查询某二维数组的矩形子区域的和。采用二维前缀和,构建二维前缀和数组:for i from 0 to m:for j from 0 to n:prefix[i+1][j+1]=prefix[i][j+1]+prefix[i+1][j]-prefix[i][j]+nums[i][j]。

参考链接:303. 区域和检索 - 数组不可变 325. 和等于 k 的最长子数组长度
525. 连续数组
304. 二维区域和检索 - 矩阵不可变

创建于2022.4.23/00.03,修改于2022.5.24/17.09

#prefix-sum