网站后台如何更换在线qq咨询代码,在线种子资源网,软件行业发展趋势,手机网站怎么做微信登陆6一.什么是前缀和算法 通俗来讲#xff0c;前缀和算法就是使用一个新数组来储存原数组中前n-1个元素的和#xff08;如果新数组的当前元素的下标为n#xff0c;计算当前元素的值为原数组中从0到n-1下标数组元素的和#xff09;#xff0c;可能这样讲起来有点抽象#xff0…一.什么是前缀和算法 通俗来讲前缀和算法就是使用一个新数组来储存原数组中前n-1个元素的和如果新数组的当前元素的下标为n计算当前元素的值为原数组中从0到n-1下标数组元素的和可能这样讲起来有点抽象我们举一个例子对其进行说明给定一个数组nums[],我们创建一个大小为nums.length1的求和数组sums[],对sum[]数组进行遍历sum[i]nums[0]nums[1]...nums[i-1](相当于nums[i-1]sum[n-1]),比如存在int[]nums{1,2,3,4},对应的前缀和数组的值为sum{0,1,3,6,10} 二.前缀和算法相对于滑动窗口具有哪些不可替代的优势及前缀和算法对算法题目的优化策略 我们在前面讲述的前缀和算法可能很多小伙伴对其的特点也有所察觉发现其与我们上一节讲到的滑动窗口有些类似我们结合下面这道题目讲讲前缀和算法对于如下这种题目而言具有怎样的解题优势 对于滑动窗口一般的解题思路如下如果当前窗口的元素大于预期条件的元素时我们将窗口的左指针向右移动如果当前窗口的元素小于预期条件的元素时我们将窗口的右指针向右移动扩大窗口但是对于上面的题目中测试用例中存在负数的情况那么对于窗口中出现了负数这种情况我们是该将窗口右移直到满足条件还是将窗口左移直到剔除这个负数呢?这明显超出了我们之前规定的对于使用滑动窗口的条件这也就是滑动窗口的局限性而根据我们对于上文中对前缀和算法的描述前缀和算法并不规定其中的元素一定要是正数或者负数我们只是将其中的元素进行相加而前缀和算法对于解决这种题目可谓大显身手。 除此之外我们讲一下前缀和算法的应用相对于我们使用暴力解法具有怎样的优化如果不创建一个新的数组来存储前n个元素的和那么此时我们每次求和时都需要从头到尾将元素和全部求一遍对于一维数组时间复杂度达到了On,但是如果我们将前面元素和进行存储每次求和只需要调用我我们前缀和数组中的元素时间复杂度只有O(1)大大降低了时间复杂度同理对于二维数组而言他可以将O(n^2)的时间复杂度降至O(1). 三.前缀和算法的模板代码
对于前缀和算法一般存在一维的前缀和与二维的前缀和这样两种不同的算法模板关于前缀和算法的模板我们使用preSum来计算数组的前缀和preSum[i]代表着前i个前i-1个数组元素的和对于二维数组preSum[i][j]则代表着行为 0到i-1列为0-j-1元素的和
一维前缀和模板
如下是一维前缀和算法的模板代码: public int[] preSum(int[] nums) {int[] preSum new int[nums.length1];for (int i 1; i nums.length; i) {preSum[i] preSum[i - 1] nums[i-1];}return preSum;}
二维前缀和模板
如下是二维前缀和的算法模板对于二维的前缀和模板是对一维前缀和模板的扩展但在本质上是完全一致的我们来描述有关二维数组的前缀和的模板 我们给出这样一个图示
对于二维数组的前缀和而言表达式可以表述为这样
每一个二维数组中的单位元素相等于绿-澄-蓝粉我们同样给出一个二维数组presum[nums.length1][nums[0].length1],presum[n][n]则代表0-n-1行0-n-1列的数据总和 、
其模板表达式如下
class NumMatrix {// 定义preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和private int[][] preSum;public NumMatrix(int[][] matrix) {int m matrix.length, n matrix[0].length;if (m 0 || n 0) return;// 构造前缀和矩阵preSum new int[m 1][n 1];for (int i 1; i m; i) {for (int j 1; j n; j) {// 计算每个矩阵 [0, 0, i, j] 的元素和preSum[i][j] preSum[i-1][j] preSum[i][j-1] matrix[i - 1][j - 1] - preSum[i-1][j-1];}}}// 计算子矩阵 [x1, y1, x2, y2] 的元素和public int sumRegion(int x1, int y1, int x2, int y2) {// 目标矩阵之和由四个相邻矩阵运算获得return preSum[x21][y21] - preSum[x1][y21] - preSum[x21][y1] preSum[x1][y1];}
}
除了完全的一维和二维的前缀和算法之外前缀和算法的题目通常会与hash等数据结构组合出题
四.关于前缀和算法的经典题目练习
1.区域和检索 - 数组不可变力扣
力扣题目描述 解题思路 这是一个完全意义上的前缀和算法的题目或者说这是一个书写前缀和算法模板的题目对于这道题我们直接使用我们前面使用的前缀和算法的模板即可创建nums.length1长度的presum[],对于presum[n],存储的是前n-1个元素的和每次求和时直接使用presum中的元素即可。 实例代码
我们给出实例代码
class Solution {public int subarraySum(int[] nums, int k) {//单纯使用前缀和无法判别从哪里进行区分这时我们需要将符合条件的数值直接存入map再次需要时直接拿来使用即可int count0;//记录最终的结果int pre0;//记录前缀和//创建mapHashMapInteger,Integermapnew HashMap();//如果是pre-target0代表从0开始刚好满足条件要求map.put(0,1);for(int i0;inums.length;i){prenums[i];if(map.containsKey(pre-k)){countmap.get(pre-k);}//将当前pre加入map.put(pre,map.getOrDefault(pre,0)1);}return count;}
}
class NumArray {//本题使用前缀和算法将使劲复杂度从On降至O1private int[]preNums;public NumArray(int[] nums) {preNumsnew int[nums.length1];//循环时创建前缀和for(int i1;ipreNums.length;i){preNums[i]preNums[i-1]nums[i-1];}}public int sumRange(int left, int right) {return preNums[right1]-preNums[left];}
} 2.和为 k 的子数组 力扣
题目描述 解题思路 这道题就是对我们一维数组前缀和算法的扩展了它不仅仅使用简单的前缀和数组进行存储数组的前缀和他同样需要使用hash表进行元素的记录和存储这是一道前缀和数组和哈希表进行融合的题目具体的解题思路如下我们对于这道题目而言难点在于对于简单的前缀和数组而言我们无法判断从哪个地方进行断开无法判断从那个地方作为起点哪个地方作为终点是符合条件的因为我们在此基础上使用哈希表哈希表中存储的是当前元素为基准的前缀和与target之间的差距如果差距为0恰好满足或者当前差距等于其前面元素的前缀和如果前面元素的前缀和为4此时前缀和-target4 前缀和比我们需要的和的值大4刚好与前面的值进行抵消这种也是符合条件的。 图示如下 实例代码
我们给出实例代码
class Solution {public int subarraySum(int[] nums, int k) {//单纯使用前缀和无法判别从哪里进行区分这时我们需要将符合条件的数值直接存入map再次需要时直接拿来使用即可int count0;//记录最终的结果int pre0;//记录前缀和//创建mapHashMapInteger,Integermapnew HashMap();//如果是pre-target0代表从0开始刚好满足条件要求map.put(0,1);for(int i0;inums.length;i){prenums[i];if(map.containsKey(pre-k)){countmap.get(pre-k);}//将当前pre加入map.put(pre,map.getOrDefault(pre,0)1);}return count;}
}
3.二维子矩阵的和力扣
题目描述 解题思路 这道题正是我们上面讲述的关于二维数组求前缀和的典型例题我们在上面模板的基础上进行思路的讲解对于红框内的元素和等于绿框元素-蓝框-红框黑框其中蓝框和红框中也有黑框的部分但是被颜色覆盖了在此之前我们首先要将元素进行初始化初始化的过程相当于对元素进行分割的逆过程单位元素加上两边的元素再减去重复的元素 实例代码
class NumMatrix {//创建二维的数组和private int[][]preNums;public NumMatrix(int[][] matrix) {preNumsnew int[matrix.length1][matrix[0].length1];//创建并遍历for(int i1;ipreNums.length;i){for(int j1;jpreNums[0].length;j){preNums[i][j]preNums[i][j-1]preNums[i-1][j]-preNums[i-1][j-1]matrix[i-1][j-1];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return preNums[row21][col21]-preNums[row21][col1]-preNums[row1][col21]preNums[row1][col1];}
} 4.除自身以外数组的乘积力扣
题目描述 解题思路 这道题目的解题思路相对而言比较巧妙它将前缀和拓展为前缀积而除了本身元素之外的其他元素的和则恰好符合前缀积中premul[i]*lastmul[i]的定义所以直接定义前缀后缀积进行元素的相乘即可 实例代码
class Solution {public int[] productExceptSelf(int[] nums) {//解题思路通过前缀积和后缀积进行相乘最终的结果就是除了nums[i]之外的相乘结果需要注意的是需要对前后缀积的含义进行一定的改变//定义前缀积int[]prenew int[nums.length];//定义后缀积int[]lastnew int[nums.length];//初始化并相乘pre[0]1;for(int i1;inums.length;i){pre[i]nums[i-1]*pre[i-1];}last[nums.length-1]1;for(int inums.length-2;i0;--i){last[i]last[i1]*nums[i1];}int[]resnew int[nums.length];//进行最后的结果返回for(int i0;inums.length;i){res[i]pre[i]*last[i];}return res;}
}
