我是靠谱客的博主 殷勤日记本,这篇文章主要介绍前缀和应用,现在分享给大家,希望可以做个参考。

文章目录

    • 一维前缀和
    • 二维前缀和

定义:前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时间复杂度。

一维前缀和

一维前缀和的公式:sum[i] = sum[i-1] + arr[i] ; sum是前缀和数组, arr是内容数组。拥有前缀和数组后, 我们可以在O(1)的时间复杂度内求出区间和

[i, j]的区间和公式: interval [i, j] = sum[j] - sum[i - 1]

leetcode:和为K的子数组

前缀和解决

首先遍历数组构建前缀和数组,在拥有前缀和数组后,通过双层循环计算数组中每一个子项与之前的子项之间的区间和(子数组的和)。时间复杂度O(n^2)

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution { public int subarraySum(int[] nums, int k) { int len=nums.length; int[] preSum=new int[len+1]; for(int i=0;i<len;i++){ preSum[i+1]=preSum[i]+nums[i]; } int result=0; for(int left=0;left<len;left++){ for(int right=left;right<len;right++){ if(preSum[right+1]-preSum[left]==k){ result++; } } } return result; } }

前缀和+哈希表

计算完包括了当前数前缀和以后,我们去查一查在当前数之前,有多少个前缀和等于 preSum - k ,这是因为满足 preSum - (preSum - k) == k 的区间的个数是我们所关心的。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution { public int subarraySum(int[] nums, int k) { int count = 0, pre = 0; HashMap < Integer, Integer > mp = new HashMap < > (); mp.put(0, 1); for (int i = 0; i < nums.length; i++) { pre += nums[i]; if (mp.containsKey(pre - k)) { count += mp.get(pre - k); } mp.put(pre, mp.getOrDefault(pre, 0) + 1); } return count; } }

二维前缀和

leetcode:二维区域和检索 - 矩阵不可变

方法来源于leetcode题解

步骤一:求 preSum

定义 preSum[i] [j]表示 从 [0,0] 位置到 [i,j] 位置的子矩形所有元素之和。

可以用下图帮助理解:S(O,D)=S(O,C)+S(O,B)−S(O,A)+D

image-20220331213031618

如果求 preSum[i] [j]表示的话,对应了以下的递推公式:

preSum[i] [j]=preSum[i-1] [j]+preSum[i] [j-1]-preSum[i-1] [j-1]+matrix[i] [j]

步骤二:根据 preSum 求子矩形面积

前面已经求出了数组中从 [0,0] 位置到 [i,j] 位置的 preSum。下面要利用 preSum[i] [j]来快速求出任意子矩形的面积。

同样利用一张图来说明:S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G)

image-20220331213054580

如果要求 [row1, col1] 到 [row2,col2] 的子矩形的面积的话,用 preSum 对应了以下的递推公式:

preSum[row2] [col2]-preSum[row2] [col1-1]-preSum[row1-1] [col2]+preSum[row1-1] [col1-1]

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumMatrix { private int[][] preSum; public NumMatrix(int[][] matrix) { if (matrix.length > 0) { preSum = new int[matrix.length + 1][matrix[0].length + 1]; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { preSum[i+1][j+1] = preSum[i][j+1] + preSum[i+1][j] - preSum[i][j] + matrix[i][j]; } } } } public int sumRegion(int row1, int col1, int row2, int col2) { return preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1] + preSum[row1][col1]; } }

最后

以上就是殷勤日记本最近收集整理的关于前缀和应用的全部内容,更多相关前缀和应用内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(54)

评论列表共有 0 条评论

立即
投稿
返回
顶部