day4_prefixSum2

本文主要是介绍day4_prefixSum2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考链接【强化练习】前缀和技巧经典习题 | labuladong 的算法笔记

一、前缀和技巧经典习题

1.523连续的子数组和

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;// 计算 nums 的前缀和int[] preSum = new int[n + 1];preSum[0] = 0;for (int i = 1; i <= n; i++) {preSum[i] = preSum[i - 1] + nums[i - 1];}// 前缀和与 k 的余数到索引的映射，方便快速查找所需的前缀和HashMap<Integer, Integer> valToIndex = new HashMap<>();for (int i = 0; i < preSum.length; i++) {// 在哈希表中记录余数int val = preSum[i] % k;// 如果这个余数还没有对应的索引，则记录下来if (!valToIndex.containsKey(val)) {valToIndex.put(val, i);}// 如果这个前缀和已经有对应的索引了，则什么都不做// 因为题目想找长度最大的子数组，所以前缀和索引应尽可能小}int res = 0;for (int i = 1; i < preSum.length; i++) {// 计算 need，使得 (preSum[i] - need) % k == 0int need = preSum[i] % k;if (valToIndex.containsKey(need)) {//获得的need(余数)对应的索引，如果索引相减 > 2，表示长度 > 2 满足条件if (i - valToIndex.get(need) >= 2) {// 这个子数组的长度至少为 2return true;}}}return false;}
}

2.连续数组

该题使用了技巧，将0和1出现次数相等的条件(子数组相加结果多种可能)，改变成相加为0(如果出现0，就向前缀和数组中加上-1)，使得该题可以用前缀和数组解决

class Solution {public int findMaxLength(int[] nums) {int n = nums.length;int[] preSum = new int[n + 1];preSum[0] = 0;// 计算 nums 的前缀和for (int i = 0; i < n; i++) {//技巧preSum[i + 1] = preSum[i] + (nums[i] == 0 ? -1 : 1);}// 前缀和到索引的映射，方便快速查找所需的前缀和HashMap<Integer, Integer> valToIndex = new HashMap<>();int res = 0;for (int i = 0; i < preSum.length; i++) {// 如果这个前缀和还没有对应的索引，说明这个前缀和第一次出现，记录下来if (!valToIndex.containsKey(preSum[i])) {valToIndex.put(preSum[i], i);} else {// 这个前缀和已经出现过了，则找到一个和为 0 的子数组res = Math.max(res, i - valToIndex.get(preSum[i]));}// 因为题目想找长度最大的子数组，所以前缀和索引应尽可能小}return res;}
}

3.和为k的子数组

这道题其实在考察前缀和技巧和哈希表的结合使用，请你先解决 523. 连续的子数组和和 525. 连续数组，然后这道题就很容易解决了。

本题和前两题的最大区别在于，需要在维护 preSum 前缀和数组的同时动态维护 count 映射，而不能等到 preSum 计算完成后再处理 count，因为 count[need] 应该维护 preSum[0..i] 中值为 need 的元素个数。

怎么理解因为 count[need] 应该维护 preSum[0..i] 中值为 need 的元素个数这句话，

举个例子，数组[0,end]索引中有 a,b,c，对应的值为v1，某个索引x值为v2，它们的大小关系是 a<b<x<c<end，且(v2 - v1)== k，当遍历到x时满足条件的子数组数量为2(preSum[x+1] - preSum[a+1] 和 preSum[x+1] - preSum[b+1])，c并不满足这个条件，所以要在计算preSum[n+1]数组的过程计算count[need]的数量，而不是在计算完preSum之后再计算，会浪费时间

class Solution {public int subarraySum(int[] nums, int k) {int n = nums.length;// 前缀和数组int[] preSum = new int[n + 1];preSum[0] = 0;// 前缀和到该前缀和出现次数的映射，方便快速查找所需的前缀和HashMap<Integer, Integer> count = new HashMap<>();
//如果某个索引的前缀和刚好等于 k，那么 need = 0，res += count.get(need); 就不会报错count.put(0, 1);// 记录和为 k 的子数组个数int res = 0;// 计算 nums 的前缀和for (int i = 1; i <= n; i++) {preSum[i] = preSum[i - 1] + nums[i - 1];// 如果之前存在值为 need 的前缀和// 说明存在以 nums[i-1] 结尾的子数组的和为 kint need = preSum[i] - k;if (count.containsKey(need)) {res += count.get(need);}// 将当前前缀和存入哈希表if (!count.containsKey(preSum[i])) {count.put(preSum[i], 1);} else {count.put(preSum[i], count.get(preSum[i]) + 1);}}return res;}
}

4. 238.除自身以外数组的乘积

(前缀 “积”) 使用前缀积乘以后缀积，获得当前res[i]的值

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;// 从左到右的前缀积，prefix[i] 是 nums[0..i] 的元素积int[] prefix = new int[n];prefix[0] = nums[0];for (int i = 1; i < nums.length; i++) {prefix[i] = prefix[i - 1] * nums[i];}// 从右到左的前缀积，suffix[i] 是 nums[i..n-1] 的元素积int[] suffix = new int[n];suffix[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--) {suffix[i] = suffix[i + 1] * nums[i];}// 结果数组int[] res = new int[n];res[0] = suffix[1]; res[n - 1] = prefix[n - 2];for (int i = 1; i < n - 1; i++) {// 除了 nums[i] 自己的元素积就是 nums[i] 左侧和右侧所有元素之积res[i] = prefix[i - 1] * suffix[i + 1];}return res;}
}