[LeetCode] 1524. Number of Sub-arrays With Odd Sum

Given an array of integers arr, return the number of subarrays with an odd sum.

Since the answer can be very large, return it modulo 109 + 7.

Example 1:
Input: arr = [1,3,5]
Output: 4
Explanation: All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:
Input: arr = [2,4,6]
Output: 0
Explanation: All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:
Input: arr = [1,2,3,4,5,6,7]
Output: 16

Constraints:
1 <= arr.length <= 105
1 <= arr[i] <= 100

和为奇数的子数组数目。

给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。

由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。

思路

思路是前缀和。我们还是像一般的前缀和题目一样，创建一个 n + 1 的数组，记录数组的前缀和，记为 presum。

再创建两个变量，分别叫做 odd 和 even，代表 presum 中前缀和是奇数的个数和前缀和是偶数的个数。

遍历 presum 数组，对于每个位置 i，如果这个位置上的前缀和 presum[i] 是偶数，那么 even++；如果这个位置上的前缀和 presum[i] 是奇数，那么 odd++。

在对 presum[i] 判断奇偶的时候，如果 presum[i] 是偶数，那么我们看看在这个位置之前出现过几次奇数，把此时的 odd 累加到 res 上；如果 presum[i] 是奇数，那么我们看看在这个位置之前出现过几次偶数，把此时的 even 累加到 res 上。举个例子，

0, x, x, j, x, x, x, x, x, i

对于任意一段子数组 [j, i] 我们如何判断他的奇偶性呢？如果 [0, i] 这一段是偶数，如果想让 [j, i] 这一段为奇数，那么 [0, j] 这一段就必须要是奇数。因为奇数 + 奇数 = 偶数。

同理，如果 [0, i] 这一段是奇数，如果想让 [j, i] 这一段为奇数，那么 [0, j] 这一段就必须要是偶数。因为偶数 + 奇数 = 奇数。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int numOfSubarrays(int[] arr) {
        int MOD = 1000000007;
		int n = arr.length;
		int[] presum = new int[n + 1];
		for (int i = 0; i < n; i++) {
			presum[i + 1] = presum[i] + arr[i];
		}

		int odd = 0;
		int even = 0;
		int res = 0;
		for (int i = 0; i < presum.length; i++) {
			if (presum[i] % 2 == 0) {
				res = (res + odd) % MOD;
				even++;
			} else {
				res = (res + even) % MOD;
				odd++;
			}
		}
		return res;
    }
}