wap网站开发视频教程,写网页用什么软件,桂林两江四湖门票多少钱,在阿里云域名可以做网站吗前缀和
前缀和是一种利用预处理的方式来减少整体实现复杂度的方法。
基本定理
假设原数列A为#xff1a;[1,2,3,4,5]#xff0c;与之对应的前缀和数列P则为#xff1a;[1,3,6,10,15]
前缀和数列的第一项等于原数列的第一项#xff0c;从第二项开始前缀和数列每一项计算…前缀和
前缀和是一种利用预处理的方式来减少整体实现复杂度的方法。
基本定理
假设原数列A为[1,2,3,4,5]与之对应的前缀和数列P则为[1,3,6,10,15]
前缀和数列的第一项等于原数列的第一项从第二项开始前缀和数列每一项计算方法为P[i] P[i-1]A[i]
原数列A与前缀和数列P则有以下几种关系
前缀和数列从第二项起每一项(i)与它的前一项(i - 1)的差等于原数列(i)的值。前缀和数列每一项(i)等于原数列中(0 ~ i)项之和。在满足0 i j时原数列的第(i ~ j)项之和等于前缀和数列的第(j)项减去第(i - 1)项。
根据这样的关系在某些应用场景上我们就可以利用前缀和进行快速求解。
1. 区域和检索 - 数组不可变
题目描述 解题思路
根据前面定理中的第三条可以发现利用前缀和可以快速实现这个需求。
代码实现
这里为了方便计算额外忽视了前缀和数列的第一位比如数列为{1,2,3,4,5}对应的前缀和数列为{0,1,3,6,10,15}其中第一位数值0没有任何含义只是为了方便处理。
class NumArray {private int[] preSum;public NumArray(int[] nums) {preSum new int[nums.length 1];for(int i 0; i nums.length; i){preSum[i 1] preSum[i] nums[i];}}public int sumRange(int left, int right) {// 本身根据定理应该是p[right] - p[left - 1]// 但由于我们将前缀和数列整体右移了一位因此就变成了p[right 1] - p[left]// 这样做的好处是不用单独处理当left为0的情况了。return preSum[right 1] - preSum[left];}
}2. 除自身以外数组的乘积
题目描述 解题思路
本题可以考虑从后向前遍历那么每一项之前的元素乘积如果用前缀和思路来处理的话就是前面定理中的第二条。符合前缀和的也符合前缀乘积
比如原数列{1,2,3,4}前缀积数列{1,2,6,24}则遍历原数列最后一位4时对应的之前所有数的乘积就是前缀积数列的倒数第二位6。
现在已经搞定了除目标元素外的左边所有元素的乘积只要再计算出其右边所有元素的乘积即可。
依据同样的思想你也可以做一个后缀积来方便直接获取但就当前这个场景来说倒也没必要对于右边元素我们只需要直接动态维护即可。
代码实现
class Solution {public int[] productExceptSelf(int[] nums) {int n nums.length;int[] preSum new int[n 1];// 前缀数列第一位无实际意思仅仅为了方便处理preSum[0] 1;for (int i 1; i n 1; i) {preSum[i] preSum[i - 1] * nums[i - 1];}// 右边元素动态维护int rightSum 1;int[] ans new int[n];for (int i n - 1; i 0; i--) {ans[i] preSum[i] * rightSum;rightSum * nums[i];}return ans;}
}3. 和相同的二元子数组
题目描述 解题思路
假设有原数列1 0 1 0 1 和与其对应的前缀和数列1 1 2 2 3。
我们知道子数组可以看作[leftright]这样一个区间并且left和right满足0 left right.所以本题可以看作是在要求0 left right这样一个区间内的所有元素和等于goal。我们看到求解0 left right这样一个区间之和就可以思考一下是否可以利用前缀和的性质。很明显在前缀和数列中只需要通过计算right - (left - 1)即可得到原数列的0 left right区间之和。经过上面3步分析最终就变成了求right - (left - 1)等于goal的个数。
所以最终我们只需要构造一个前缀和数列然后通过嵌套循环的方式以每个right为子数组的结束区间挨个检查子数组的开始区间即可。
public int numSubarraysWithSum(int[] nums, int goal) {int[] perSum new int[nums.length 1];for (int i 0; i nums.length; i) {perSum[i 1] perSum[i] nums[i];}int ans 0;for (int right 1; right perSum.length; right) {for (int left right; left 0; left--) {if (perSum[right] - perSum[left - 1] goal) {ans;}}}return ans;
}复杂度优化
由于存在嵌套循环因此复杂度较高不难发现每次内层循环中只是在计算在0~right-1下标对应的数值中有多少个等于perSum[right] - goal因此我们考虑将每一个0~right-1对应的结果直接记录下来这样不就可以省去内层循环的处理了吗~
public int numSubarraysWithSum(int[] nums, int goal) {int[] perSum new int[nums.length 1];for (int i 0; i nums.length; i) {perSum[i 1] perSum[i] nums[i];}int ans 0;// key表示前缀和数列坐标对应的值value表示改值出现的次数MapInteger, Integer map new HashMap();// 前缀和第一位坐标0需特殊处理一下对应的值为0出现1次。map.put(0, 1);for (int right 1; right perSum.length; right) {if (map.containsKey(perSum[right] - goal)) {ans map.get(perSum[right] - goal);}map.put(perSum[right], map.getOrDefault(perSum[right], 0) 1);}return ans;
}如果还想简化一点则可以动态维护前缀和数组如下
public int numSubarraysWithSum(int[] nums, int goal) {int ans 0;MapInteger, Integer map new HashMap();map.put(0, 1);int perSum 0;for (int right 0; right nums.length; right) {perSum nums[right];if (map.containsKey(perSum - goal)) {ans map.get(perSum - goal);}map.put(perSum, map.getOrDefault(perSum, 0) 1);}return ans;
}类似题型
与之类似的题目还有
560.和为K的子数组
974.和可被 K 整除的子数组
4. 连续的子数组和
题目描述 解题思路
本题关键在于解决子数组元素总和为K的倍数这个问题。
首先我们发现是求解子数组的问题通过前面的练习我们知道在前缀和数列中求解子数组的和等同于求解其前缀和数组的right - (left - 1)。 同余定理 给定一个正整数m如果两个整数a和b满足a-b能够被m整除即(a-b)/m得到一个整数那么就称整数a与b对模m同余记作a≡b(mod m)。 因此如果(right - (left - 1))是K的整数倍则根据同余定理则有 right % k (left - 1) % k。
有了这个结论以后接下来的处理方式就和前面差不多了通过一个哈希表用Key记录每一项的余数Value用来记录下标为了满足题目中大小至少为2的要求下标位置不更新。
代码实现
public boolean checkSubarraySum(int[] nums, int k) {int sum 0;MapInteger, Integer map new HashMap();map.put(0, -1);for (int i 0; i nums.length; i) {sum nums[i];int mod sum % k;if (map.containsKey(mod)) {if (i - map.get(mod) 2) {return true;}} else {map.put(mod, i);}}return false;
}5. 连续数组
题目描述 解题思路
如果把拥有相同数量的0和1理解为互相抵消假设我们有一个计数器C当遇到0就减1遇到1就加1因此当C等于0时则0和1的数量一定相同所以这个题目就又变成了子数组求和的问题了那么看到子数组求和就想到用前缀和数列来解。
我们知道子数组可以看作[leftright]其所有元素之和又等于其对应的前缀和数列right - (left - 1)的计算结果这个在前面几题中也一直在用又因为如果right (left - 1)则right - (left - 1)0也就是我们要求的结果子数组区间内所有元素之和为0。所以最后我们要求的其实就是长度最长的right (left - 1)。
代码实现
public int findMaxLength(int[] nums) {MapInteger, Integer map new HashMap();// 表示0值出现的下标位置map.put(0, -1);int sum 0;int ans 0;for (int i 0; i nums.length; i) {sum nums[i] 0 ? -1 : 1;if (map.containsKey(sum)) {ans Math.max(ans, i - map.get(sum));} else {map.put(sum, i);}}return ans;
}类似题型
与之类似的题目还有
字母与数字
6. 和为奇数的子数组数目
题目描述 解题思路
还是求子数组和的问题要求为奇数我们知道两奇数或两偶数相加结果为偶数只有一奇一偶相加结果才为奇数。
所以根据right - (left - 1)等于原数组的子数组之和可以得出以下结论 当right为偶数时left - 1必须为奇数子数组之和才为奇数。 当right为奇数时left - 1必须为偶数子数组之和才为奇数。
代码实现
public int numOfSubarrays(int[] arr) {int ans 0;int mod 1000000007;int odd 0;int even 1;int sum 0;for (int i 0; i arr.length; i) {sum arr[i];ans (ans (sum % 2 0 ? odd : even)) % mod;if(sum % 2 0){even;}else{odd;}}return ans;
}7. 统计「优美子数组」
题目描述 解题思路
可以把奇数的个数当做前缀和数列来记录比如对于[1,1,2,1,1]这样的数列对应的奇数前缀和数列为[0,1,2,2,3,4]每一项表示的是奇数个数注意0个奇数也是有计算含义的。
那么如果子数组恰好有K个奇数则有right - (left - 1) K转换一下也就是right - K left - 1这就回到了我们习惯的哈希表处理方式无需说明直接看代码。
代码实现
public int numberOfSubarrays(int[] nums, int k) {int ans 0;int oddCnt 0;MapInteger, Integer map new HashMap();// 初始化map表示出现0个奇数的次数为1map.put(0, 1);for (int i 0; i nums.length; i) {if (nums[i] % 2 ! 0) {oddCnt;}if (map.containsKey(oddCnt - k)) {ans map.get(oddCnt - k);}map.put(oddCnt, map.getOrDefault(oddCnt, 0) 1);}return ans;
}
