【Java算法专场】前缀和（下）

目录

和为 K 的子数组

算法分析

算法步骤

算法代码

算法示例

和可被 K 整除的子数组

算法分析

同余定理

负数取余

算法步骤

算法代码

算法示例

连续数组

算法分析

算法步骤

算法代码

算法示例

矩阵区域和

算法分析

算法步骤

算法代码

算法示例

---

算法分析

本道题是要在数组中查找和为k的子数组，如果我们使用暴力解法，时间复杂度为O(N^2)。对于这种求子数组和的问题，我们可以使用前缀和来解决。

算法步骤

1. 初始化：定义一个sum，初始化为0，用来计算数组中元素和；定义一个HashMap用来存储数组中的前缀和，还有值的出现次数（此处需要添加(0,1),若sum-k刚好等于0的情况）。定义一个ans用来计算数组中有多少个和为k的子数组。

2. 遍历数组：将数组中的元素累加到sum中，同时在HashMap中判断此时的sum是否存在，若存在，则将其键值添加到ans中。当添加完之后，将此时的sum添加到Hashmap中。

3. 返回ans：当遍历完数组，此时返回ans即可。

算法代码

/*** 计算一个数组中连续子数组和等于给定值k的子数组个数* 该方法使用前缀和的概念来加速计算过程，通过HashMap记录每个前缀和出现的次数** @param nums 整数数组，其中nums[i]表示子数组的元素* @param k 目标和，表示连续子数组的和* @return 返回连续子数组和等于k的子数组个数*/public int subarraySum(int[] nums, int k) {// 初始化当前前缀和为0int sum=0;// 初始化结果变量为0，用于记录找到的子数组个数int ans=0;// 使用HashMap来存储每个前缀和出现的次数HashMap<Integer,Integer> hash=new HashMap<>();// 将前缀和0的出现次数设置为1，表示前缀和为0的出现了一次hash.put(0,1);// 遍历数组中的每个元素for(int x:nums){// 累加当前元素到前缀和sum+=x;// 如果当前前缀和减去目标和的值已经出现过，则说明找到了一个或多个和为k的子数组// 将其出现次数加到结果变量中ans+=hash.getOrDefault(sum-k,0);// 更新HashMap，记录当前前缀和的出现次数// 如果当前前缀和不存在，则默认为0，然后加1hash.put(sum,hash.getOrDefault(sum,0)+1);}// 返回找到的子数组个数return ans;}

时间复杂度为O(n),n为数组长度，只遍历一遍数组，hash的查找速度为O(1).

空间复杂度为O(n),最坏情况下hash存储的个数刚好是n个，n是数组长度。

算法示例

以nums = [1,2,3], k = 3为例

第一步：初始化

sum=0,ans=0,hash={(0,1)}

第二步：遍历数组

1. sum+=1,ans+=0,hash={(0,1),(1,1)}
2. sum=3, sum-k=0,此时hash中key为0的键值为1，ans+1,ans=1,hash={(0,1),(1,1),(3,1)}
3. sum=6,sum-k=3,此时hash中key为3的键值为1，ans+1,ans=2,hash={(0,1),(1,1),(3,1),(6,1)}.

第三步：返回ans

此时ans=2，返回即可。

和可被 K 整除的子数组

算法分析

本道题与上一道题类似，不过这道题求和能被K整除的子数组。若使用暴力解法，时间复杂度为O(n^2)。但我们可以使用更好的方法来优化。那就是前缀和。

在讲这道题之前，我们先来了解一下什么是同余定理

同余定理

给定一个正整数 m，如果两个整数 a 和 b 满足 m|(a-b)，即 a-b 能够被 m 整除，或者 (a-b)/m 得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 a≡b(mod m)。对模 m 同余是整数的一个等价关系。这里我们不做过多介绍（想要了解的更清楚可以去查一下）。

(A-B)%m=0 <==> A%m=B%m

示例：(5-3)%2=0  <=> 5%2=1  3%2=1

负数取余

负数%整数=负数

但我们这里需要的正数，所以我们可以在A%m之后再加上m之后就可以得到一个正数。同时，可能A本身是一个正数，那么取余之后再加上m，就有点多余了，所有我们这里在+m之后还需对其再模一次m，即（A%m+m）%m.

算法步骤

1. 初始化：定义一个ans并初始化为0；定义一个sum并初始化为0，用来累加数组和；定义一个HashMap，Key用来记录余数，values用来记录余数出现的次数。
2. 遍历数组：让sum累加数组中的元素。同时，当sum累加一个元素之后，此时需要在hashmap查看是否有以【(sum%k+k)%k】为键的键值对。如果当前前缀和的余数已经出现过，则说明找到了一个或多个能被k整除的子数组,则将此键值对下的键值加到ans中。当加完之后，将sum此时的余数映射到hashmap中，并将其键值+1.
3. 处理细节：此处有可能sum的余数为0，所以我们需要在遍历之前先添加一个(0,1).
4. 返回结果：当遍历完数组之后，此时返回ans即可。

算法代码

    /*** 计算数组中前缀和能被k整除的子数组数量* * @param nums 输入的整数数组* @param k 整数k，用于判断子数组的和是否能被k整除* @return 返回满足条件的子数组数量*/public int subarraysDivByK(int[] nums, int k) {// 用于计算前缀和int sum=0;// 用于记录满足条件的子数组数量int ans=0;// 使用HashMap来存储每个前缀和的出现次数HashMap<Integer,Integer> hash=new HashMap<>();for(int x:nums){// 累加当前元素到前缀和sum+=x;// 如果当前前缀和减去目标和的值已经出现过，则说明找到了一个或多个和为k的子数组ans+=hash.getOrDefault((sum%k+k)%k,0);// 更新HashMap，记录当前前缀和的出现次数hash.put((sum%k+k)%k,hash.getOrDefault((sum%k+k)%k,0)+1);}}

时空复杂度为O(n),n为数组长度，整个过程，只遍历了一遍数组。在最坏情况下，可能hash的键值对有n个。 

算法示例

以nums = [4,5,0,-2,-3,1], k = 5为例

第一步：初始化

sum=0,ans=0.hash={(0,1)};

第二步：遍历数组

（记余数为mod）

1. sum+=nums[0]=4,mod=(4%5+5)%5=4,此时hash中不存在以4为键的键值对，添加到hash中，hash={(0,1),(4,1)}
2. sum+=nums[1]=4+5=9,mod=(9%5+5)%5=4.此时hash存在以4为键的键值对，键值为1，此时ans+1=1，更新键值，hash={(0,1),(4,2)}
3. sum+=nums[2]=9+0=9,mod=(9%5+5)%5=4,此时hash存在以4为键的键值对，键值为2，此时ans+2=3，更新键值，hash={(0,1),(4,3)}
4. sum+nums[3]=9-2=6,mod=(7%5+5)%5=2,此时hash不存在以2为键的键值对，添加到hash中，hash=｛(0,1),(4,3),(2,1)｝
5. sum+nums[4]=7-3=4,mod=(4%5+5)%5=4,此时hash存在以4为键的键值对，键值为3，此时ans+3=6，更新键值，hash=｛(0,1),(4,4),(2,1)｝
6. sun+nums[5]=4+1=5,mod=(5%5+5)%5=0,此时hash存在以0为键的键值对，键值为1，此时ans+1=7，更新键值，hash=｛(0,2),(4,4),(2,1)｝

第三步：返回结果

此时已经遍历完数组，ans=7，返回ans即可。

连续数组

算法分析

本道题与第一道和为k的子数组类似，但本道题要求的在一个二进制数组中找具有相同数量0和1的最长子数组。若用暴力解法，时间复杂度为O(n^2),但我们这里可以使用前缀和。让时间复杂度达到O(n).

算法步骤

1. 初始化：定义ans并初始化为0，定义sum，用来计算每次遍历到的位置之前的差值；定义hash，用来存放sum以及其在数组中的索引。同时需要将以0为键的键值设置为-1，这是为了防止在0处就出现了相同数量的0和1.
2. 遍历数组：在将nums[i]添加到sum时，如果nums[i]是0，那么就视为-1，反之，若是1，则直接累加到数组中。通过-1和1，我们就能算出0和1此时的差值。
3.  查看0和1的数量：每次更新完sum的值，我们都需要判断sum是否已经在hash中；若已经在hash中，我们则直接更新ans的值,ans=Math.max(ans,i-hash.get(sum))。若此时sum不存在hash中，就将sum及其索引i添加到hash中，即hash.put(sum,i)。
4. 返回结果：当我们遍历完数组，此时就可以将ans返回。

算法代码

/*** 寻找给定数组中最长的连续子数组，使得子数组中0和1的个数相等** @param nums 一个只包含0和1的整数数组* @return 返回满足条件的最长子数组的长度*/public int findMaxLength(int[] nums) {// sum用于记录数组遍历过程中的0和1的累积差值int sum=0;// ans用于记录满足条件的最长子数组的长度int ans=0;// 使用HashMap来存储每个累积差值首次出现的索引位置HashMap<Integer,Integer> hash=new HashMap<>();// 初始化sum为0，并将0作为HashMap的初始索引位置hash.put(0,-1);// 遍历数组，计算累积差值，并更新最长子数组的长度for(int i=0;i<nums.length;i++){// 如果当前元素为0，则将sum减1，否则将sum加1sum+=(nums[i]==0?-1:1);// 如果当前累积差值已经在HashMap中存在，则找到了一个满足条件的子数组if(hash.containsKey(sum)) {// 更新最长子数组的长度ans=Math.max(ans,i-hash.get(sum));} else {// 如果当前累积差值首次出现，则将其索引位置存入HashMaphash.put(sum,i);}}// 返回最长子数组的长度return ans;}

时空复杂度为O(n),n为数组长度，整个过程只遍历了一遍数组，在最坏情况下，hash的键值对可能是O(n). 

算法示例

以nums = [0,1,0]为例

第一步：初始化

ans=0,sum=0,hash={(0,-1)};

第二步：遍历数组

1. sum+=nums[0]=-1,此时hash中不存在以-1为键的键值对，将其添加到hash中，hash={(0,-1),(-1,0)}
2. sum+=nums[1]=-1+1=0,此时hash中存在以0为键的键值对，键值为-1。此时索i=1,ans=1-(-1)=2。
3. sum+=nums[2]=0-1=-1,此时hash中存在以-1为键的键值对，键值为1，此时索引i=2，ans=2-0=2。

第三步：返回结果

此时已经遍历完数组，ans=2，返回即可。

矩阵区域和

算法分析

本道题看起来难理解，其实就是那就通过下图来进行理解。

不难看出，其实题目要计算的，其实就是要计算向外扩大k个方格的矩阵的和并将计算出以每个点为中心的矩阵和以一个新的矩阵返回。 

算法步骤

1. 初始化：定义n并初始化为mat数组的行数，定义m并初始化为mat[0].length，即列的长度。创建一个（n+1）*（m+1）的二维前缀和数组dp。
2. 预处理dp数组：在上一篇我们已经讲过如何实现一个dp数组，这里我直接上式子:dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1],为什么是mat[i-1][j-1],在前面我们的二维数组是从1下标开始的，但这里是从0开始，所以dp[i][j]中对应mat中的mat[i-1][j-1].
3. 定义ret结果矩阵：这里我们定义个大小为(n*m)的ret二维数组，用来存放矩阵和。
4. 定义坐标：这里我们需要定义矩阵的左上角坐标(x1,y1),以及右下角坐标(x2,y2).在计算坐标时，由于dp是从1开始，而ret是从0开始的，所以我们在dp中取值时，坐标都要+1，同时需要考虑当前索引下的i-k和i-j是否越界。依据上述：x1=Math.max(0,i-k)+1  y1=Math.max(0,j-k)+1;  x2=Math.min(n-1,i+k)+1  y2=Math.min(m-1,j+k)+1.
5. 计算结果：当完成坐标的计算，那么我们就可以根据ret[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]计算矩阵和
6. 返回ret矩阵：当完成计算之后，我们返回ret矩阵即可。

算法代码

/*** 计算矩阵中每个元素的块和** @param mat 输入的矩阵* @param k 块的大小参数* @return 每个元素的块和构成的新矩阵*/public int[][] matrixBlockSum(int[][] mat, int k) {// 获取矩阵的行数int n = mat.length;// 获取矩阵的列数int m = mat[0].length;// 初始化二维前缀和数组，大小为矩阵大小加1，用于方便计算int[][] dp = new int[n + 1][m + 1];// 遍历矩阵，计算二维前缀和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 当前元素的二维前缀和等于其上方、左方和左上方元素的前缀和加上当前元素值dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];}}// 初始化结果矩阵，用于存放每个元素的块和int[][] ret = new int[n][m];// 遍历矩阵，计算每个元素的块和for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 计算块的左上角坐标int x1 = Math.max(0, i - k)+1;int y1 = Math.max(0, j - k)+1;// 计算块的右下角坐标int x2 = Math.min(n - 1, i + k)+1;int y2 = Math.min(m - 1, j + k)+1;// 计算当前元素的块和，减去不需要的部分ret[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];}}// 返回结果矩阵return ret;}

时空复杂度为O(n*m),n*m是数组的大小，整个过程需要开辟两个数组。 

算法示例

以mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1为例

这里不做太多说明，上图！

---

以上就是前缀和算法的专题训练，就先到这里了~

若有不足，欢迎指正~