前缀和数组
学习自 小而美的算法技巧：前缀和数组
303. 区域和检索 - 数组不可变
304. 二维区域和检索 - 矩阵不可变
560. 和为 K 的子数组
1314. 矩阵区域和
区分是用前缀和还是用滑动窗口的关键是：元素是否有负数
一维前缀和
为了将前缀和数组下标与原数组下标对应，
前缀和数组长度为 n+1
此时前缀和数组 i 位置元素代表 原数组中 前 i 个元素之和。
class NumArray {
int []arr;
public NumArray(int[] nums) {
arr = new int [nums.length+1];
arr[0]=nums[0];
for(int i =1 ; i<arr.length;i++){
arr[i] = arr[i-1]+nums[i-1];
}
}
public int sumRange(int left, int right) {
return arr[right+1]-arr[left];
}
}
二维前缀和
二维矩阵前缀和
同样的，为了方便管理
我们在建立前缀和数组时，行数、列数均要比原数组多1
前缀和数组 arr [ 1 ] [ 1 ] 代表原来数组中 第一行到第一行 与第一列到第一列 的矩阵元素之和
比如
原数组：
3 1
5 6
它的前缀和数组为
0 0 0
0 3 3+1
0 3+5 3+1+5+6arr [ 2 ] [ 2 ] 代表原来数组中 第一行到第二行 与第一列到第二列 的矩阵元素之和
这种条件下建立的前缀和数组的【i，j 】元素代表 原数组 中 从【0，0】 到【i-1，j-1】 所围成的矩形内的元素之和。
class NumMatrix {
int [][] arr ;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
if (m == 0 || n == 0) return;
arr = new int [m+1][n+1];
// 第一行 第一列 无实际意义 从行列都是1 开始遍历
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
arr[i][j]=arr[i-1][j]+arr[i][j-1]+matrix[i-1][j-1]-arr[i-1][j-1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return arr[row2+1][col2+1]-arr[row1][col2+1]-arr[row2+1][col1]+arr[row1][col1];
}
}
在求解前缀和数组 arr【i，j】 个位置的前缀和时，需要利用到
arr【i-1，j】
arr【i，j-1】
arr【i-1,j-1】
原数组【i，j】
这四个位置的元素
图源leetcode-笨猪爆破组-题解
因为arr【i，j】 可以分为四部分，也就是上图的四种颜色不同的矩阵。
利用之前已经计算好的元素之和，来减少当前元素的计算量，要不然每次都遍历【i，j】内的元素再累加，时间负责度是很高的。
实现 【i，j】到 【m，n】 （m>= i , n >=j ） 围成的矩形内的元素之和
//s(O,F) = arr[x1][y2+1]
//s(O,E) = arr[x2+1][ y1]
//arr[x1][y1] 其实就是左上角的那一部分，因为多减去了一次这部分的面积，所以要加回来。
arr[x2+1][y2+1]-arr[x1][y2+1]-arr[x2+1][y1]+arr[x1][y1]
前缀和思想
暴力法
生成前缀和数组，然后每两个位置减一次，如果值为目标数字，res+1
能过，但是不优雅。
int subarraySum(int[] nums, int k) {
int n = nums.length;
// 构造前缀和
int[] sum = new int[n + 1];
sum[0] = 0;
for (int i = 0; i < n; i++)
sum[i + 1] = sum[i] + nums[i];
int ans = 0;
// 穷举所有子数组
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
// sum of nums[j..i-1]
if (sum[i] - sum[j] == k)
ans++;
return ans;
}
由于只关心次数，不关心具体的解，我们可以使用哈希表加速运算
看了很多人写的帖子来描述这个最优解，我最终找到了这个我能真正理解的版本
因为时间复杂度最大支出是这部分，可以考虑从这优化
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (sum[i] - sum[j] == k)
ans++;
第二层 for 循环在干嘛呢？翻译一下就是，在计算，有几个j能够使得sum[i]和sum[j]的差为 k。毎找到一个这样的j，就把结果加一。
sum[ i ] - sum [ j ] == k
交换一下 变量顺序
if (sum[j] == sum[i] - k)
ans++;
如果可以实现直接记录下 有多少次 sum [ j ] 和sum[ i ]-k相等 ，那就相当于求出了结果。
因为不求具体是哪些元素，只求次数，所以可以用map在生成前缀和过程中记录下
每一个前缀和出现的次数将其放入map中，并实时更新
然后当下次更新前，判断是否有 sum - k 在map 中，如果有就加上该前缀和出现的次数。
代码：
class Solution {
public int subarraySum(int[] nums, int k) {
// key：前缀和，value：key 对应的前缀和的个数
Map<Integer, Integer> preSumFreq = new HashMap<>();
// 对于下标为 0 的元素，前缀和为 0，个数为 1
//例如输入[1,1,0]，k = 2 如果没有这行代码，则会返回0,漏掉了1+1=2，和1+1+0=2的情况
//输入：[3,1,1,0] k = 2时则不会漏掉
//因为presum[3] - presum[0]表示前面 3 位的和，所以需要map.put(0,1),垫下底
//例子来源：作者：chefyuan
//链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/de-liao-yi-wen-jiang-qian-zhui-he-an-pai-yhyf/
preSumFreq.put(0, 1);
int preSum = 0;
int count = 0;
for (int num : nums) {
preSum += num;
// 先获得前缀和为 preSum - k 的个数，加到计数变量里
if (preSumFreq.containsKey(preSum - k)) {
// System.out.println("num= " + num +" preSum= "+ preSum + " preSum-k= " + (preSum-k));
// System.out.println("之前 count ="+count );
count += preSumFreq.get(preSum - k);
//System.out.println("之后 count ="+count );
}
// 然后维护 preSumFreq 的定义
preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
}
return count;
}
}
类似该算法思想的题：
其他前缀和题目：