成都建设网站制作,常德网络建站,企业做网站收入,免费做外贸网站目录
和为 K 的子数组
算法分析
算法步骤
算法代码
算法示例
和可被 K 整除的子数组
算法分析
同余定理
负数取余
算法步骤
算法代码
算法示例
连续数组
算法分析
算法步骤
算法代码
算法示例
矩阵区域和
算法分析
算法步骤
算法代码
算法示例 算法分析 …
目录
和为 K 的子数组
算法分析
算法步骤
算法代码
算法示例
和可被 K 整除的子数组
算法分析
同余定理
负数取余
算法步骤
算法代码
算法示例
连续数组
算法分析
算法步骤
算法代码
算法示例
矩阵区域和
算法分析
算法步骤
算法代码
算法示例 算法分析
本道题是要在数组中查找和为k的子数组如果我们使用暴力解法时间复杂度为O(N^2)。对于这种求子数组和的问题我们可以使用前缀和来解决。
算法步骤 初始化定义一个sum初始化为0用来计算数组中元素和定义一个HashMap用来存储数组中的前缀和还有值的出现次数此处需要添加(0,1),若sum-k刚好等于0的情况。定义一个ans用来计算数组中有多少个和为k的子数组。 遍历数组将数组中的元素累加到sum中同时在HashMap中判断此时的sum是否存在若存在则将其键值添加到ans中。当添加完之后将此时的sum添加到Hashmap中。 返回ans当遍历完数组此时返回ans即可。
算法代码
/*** 计算一个数组中连续子数组和等于给定值k的子数组个数* 该方法使用前缀和的概念来加速计算过程通过HashMap记录每个前缀和出现的次数** param nums 整数数组其中nums[i]表示子数组的元素* param k 目标和表示连续子数组的和* return 返回连续子数组和等于k的子数组个数*/public int subarraySum(int[] nums, int k) {// 初始化当前前缀和为0int sum0;// 初始化结果变量为0用于记录找到的子数组个数int ans0;// 使用HashMap来存储每个前缀和出现的次数HashMapInteger,Integer hashnew HashMap();// 将前缀和0的出现次数设置为1表示前缀和为0的出现了一次hash.put(0,1);// 遍历数组中的每个元素for(int x:nums){// 累加当前元素到前缀和sumx;// 如果当前前缀和减去目标和的值已经出现过则说明找到了一个或多个和为k的子数组// 将其出现次数加到结果变量中anshash.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为例 第一步初始化
sum0,ans0,hash{(0,1)}
第二步遍历数组
sum1,ans0,hash{(0,1),(1,1)}sum3, sum-k0,此时hash中key为0的键值为1ans1,ans1,hash{(0,1),(1,1),(3,1)}sum6,sum-k3,此时hash中key为3的键值为1ans1,ans2,hash{(0,1),(1,1),(3,1),(6,1)}.
第三步返回ans
此时ans2返回即可。
和可被 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)%m0 A%mB%m
示例(5-3)%20 5%21 3%21
负数取余
负数%整数负数
但我们这里需要的正数所以我们可以在A%m之后再加上m之后就可以得到一个正数。同时可能A本身是一个正数那么取余之后再加上m就有点多余了所有我们这里在m之后还需对其再模一次m即A%mm%m.
算法步骤
初始化定义一个ans并初始化为0定义一个sum并初始化为0用来累加数组和定义一个HashMapKey用来记录余数values用来记录余数出现的次数。遍历数组让sum累加数组中的元素。同时当sum累加一个元素之后此时需要在hashmap查看是否有以【(sum%kk)%k】为键的键值对。如果当前前缀和的余数已经出现过则说明找到了一个或多个能被k整除的子数组,则将此键值对下的键值加到ans中。当加完之后将sum此时的余数映射到hashmap中并将其键值1.处理细节此处有可能sum的余数为0所以我们需要在遍历之前先添加一个(0,1).返回结果当遍历完数组之后此时返回ans即可。
算法代码 /*** 计算数组中前缀和能被k整除的子数组数量* * param nums 输入的整数数组* param k 整数k用于判断子数组的和是否能被k整除* return 返回满足条件的子数组数量*/public int subarraysDivByK(int[] nums, int k) {// 用于计算前缀和int sum0;// 用于记录满足条件的子数组数量int ans0;// 使用HashMap来存储每个前缀和的出现次数HashMapInteger,Integer hashnew HashMap();for(int x:nums){// 累加当前元素到前缀和sumx;// 如果当前前缀和减去目标和的值已经出现过则说明找到了一个或多个和为k的子数组anshash.getOrDefault((sum%kk)%k,0);// 更新HashMap记录当前前缀和的出现次数hash.put((sum%kk)%k,hash.getOrDefault((sum%kk)%k,0)1);}}时空复杂度为O(n),n为数组长度整个过程只遍历了一遍数组。在最坏情况下可能hash的键值对有n个。
算法示例 以nums [4,5,0,-2,-3,1], k 5为例 第一步初始化
sum0,ans0.hash{(0,1)};
第二步遍历数组
记余数为mod
sumnums[0]4,mod(4%55)%54,此时hash中不存在以4为键的键值对添加到hash中hash{(0,1),(4,1)}sumnums[1]459,mod(9%55)%54.此时hash存在以4为键的键值对键值为1此时ans11更新键值hash{(0,1),(4,2)}sumnums[2]909,mod(9%55)%54,此时hash存在以4为键的键值对键值为2此时ans23更新键值hash{(0,1),(4,3)}sumnums[3]9-26,mod(7%55)%52,此时hash不存在以2为键的键值对添加到hash中hash(0,1),(4,3),(2,1)sumnums[4]7-34,mod(4%55)%54,此时hash存在以4为键的键值对键值为3此时ans36更新键值hash(0,1),(4,4),(2,1)sunnums[5]415,mod(5%55)%50,此时hash存在以0为键的键值对键值为1此时ans17更新键值hash(0,2),(4,4),(2,1)
第三步返回结果
此时已经遍历完数组ans7返回ans即可。
连续数组 算法分析
本道题与第一道和为k的子数组类似但本道题要求的在一个二进制数组中找具有相同数量0和1的最长子数组。若用暴力解法时间复杂度为O(n^2),但我们这里可以使用前缀和。让时间复杂度达到O(n).
算法步骤
初始化定义ans并初始化为0定义sum用来计算每次遍历到的位置之前的差值定义hash用来存放sum以及其在数组中的索引。同时需要将以0为键的键值设置为-1这是为了防止在0处就出现了相同数量的0和1.遍历数组在将nums[i]添加到sum时如果nums[i]是0那么就视为-1反之若是1则直接累加到数组中。通过-1和1我们就能算出0和1此时的差值。 查看0和1的数量每次更新完sum的值我们都需要判断sum是否已经在hash中若已经在hash中我们则直接更新ans的值,ansMath.max(ans,i-hash.get(sum))。若此时sum不存在hash中就将sum及其索引i添加到hash中即hash.put(sum,i)。返回结果当我们遍历完数组此时就可以将ans返回。
算法代码
/*** 寻找给定数组中最长的连续子数组使得子数组中0和1的个数相等** param nums 一个只包含0和1的整数数组* return 返回满足条件的最长子数组的长度*/public int findMaxLength(int[] nums) {// sum用于记录数组遍历过程中的0和1的累积差值int sum0;// ans用于记录满足条件的最长子数组的长度int ans0;// 使用HashMap来存储每个累积差值首次出现的索引位置HashMapInteger,Integer hashnew HashMap();// 初始化sum为0并将0作为HashMap的初始索引位置hash.put(0,-1);// 遍历数组计算累积差值并更新最长子数组的长度for(int i0;inums.length;i){// 如果当前元素为0则将sum减1否则将sum加1sum(nums[i]0?-1:1);// 如果当前累积差值已经在HashMap中存在则找到了一个满足条件的子数组if(hash.containsKey(sum)) {// 更新最长子数组的长度ansMath.max(ans,i-hash.get(sum));} else {// 如果当前累积差值首次出现则将其索引位置存入HashMaphash.put(sum,i);}}// 返回最长子数组的长度return ans;}时空复杂度为O(n),n为数组长度整个过程只遍历了一遍数组在最坏情况下hash的键值对可能是O(n).
算法示例 以nums [0,1,0]为例 第一步初始化
ans0,sum0,hash{(0,-1)};
第二步遍历数组
sumnums[0]-1,此时hash中不存在以-1为键的键值对将其添加到hash中hash{(0,-1),(-1,0)}sumnums[1]-110,此时hash中存在以0为键的键值对键值为-1。此时索i1,ans1-(-1)2。sumnums[2]0-1-1,此时hash中存在以-1为键的键值对键值为1此时索引i2ans2-02。
第三步返回结果
此时已经遍历完数组ans2返回即可。 矩阵区域和 算法分析
本道题看起来难理解其实就是那就通过下图来进行理解。 不难看出其实题目要计算的其实就是要计算向外扩大k个方格的矩阵的和并将计算出以每个点为中心的矩阵和以一个新的矩阵返回。
算法步骤
初始化定义n并初始化为mat数组的行数定义m并初始化为mat[0].length即列的长度。创建一个n1*m1的二维前缀和数组dp。预处理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].定义ret结果矩阵这里我们定义个大小为(n*m)的ret二维数组用来存放矩阵和。定义坐标这里我们需要定义矩阵的左上角坐标(x1,y1),以及右下角坐标(x2,y2).在计算坐标时由于dp是从1开始而ret是从0开始的所以我们在dp中取值时坐标都要1同时需要考虑当前索引下的i-k和i-j是否越界。依据上述x1Math.max(0,i-k)1 y1Math.max(0,j-k)1; x2Math.min(n-1,ik)1 y2Math.min(m-1,jk)1.计算结果当完成坐标的计算那么我们就可以根据ret[i][j]dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]计算矩阵和返回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为例
这里不做太多说明上图 以上就是前缀和算法的专题训练就先到这里了~
若有不足欢迎指正~
