LeetCode-数组-前缀和-中等难度

前缀和

前缀和是一种利用预处理的方式来减少整体实现复杂度的方法。

基本定理

假设原数列A为：[1,2,3,4,5]，与之对应的前缀和数列P则为：[1,3,6,10,15]

前缀和数列的第一项等于原数列的第一项，从第二项开始前缀和数列每一项计算方法为：P[i] = P[i-1]+A[i]

原数列A与前缀和数列P则有以下几种关系：

1. 前缀和数列从第二项起，每一项(i)与它的前一项(i - 1)的差等于原数列(i)的值。
2. 前缀和数列每一项(i)等于原数列中(0 ~ i)项之和。
3. 在满足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。

1. 我们知道子数组可以看作[left，right]这样一个区间，并且left和right满足：0 <= left <= right.
2. 所以本题可以看作是在要求0 <= left <= right这样一个区间内的所有元素和等于goal。
3. 我们看到求解0 <= left <= right这样一个区间之和，就可以思考一下是否可以利用前缀和的性质。很明显在前缀和数列中只需要通过计算right - (left - 1)，即可得到原数列的0 <= left <= right区间之和。
4. 经过上面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表示改值出现的次数Map<Integer, 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;Map<Integer, 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;Map<Integer, 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的数量一定相同，所以这个题目就又变成了子数组求和的问题了，那么看到子数组求和就想到用前缀和数列来解。

我们知道子数组可以看作[left，right]，其所有元素之和，又等于其对应的前缀和数列right - (left - 1)的计算结果，这个在前面几题中也一直在用，又因为如果right == (left - 1)，则right - (left - 1)==0，也就是我们要求的结果，子数组区间内所有元素之和为0。所以，最后我们要求的其实就是长度最长的right == (left - 1)。

代码实现

public int findMaxLength(int[] nums) {Map<Integer, 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)等于原数组的子数组之和，可以得出以下结论：

1. 当right为偶数时，left - 1必须为奇数，子数组之和才为奇数。

2. 当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;Map<Integer, 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;
}