1524. 和为奇数的子数组数目

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

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

示例 1：

输入：arr = [1,3,5]
输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ，所以答案为 4 。
示例 2 ：

输入：arr = [2,4,6]
输出：0
解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数，所以答案为 0 。
示例 3：

输入：arr = [1,2,3,4,5,6,7]
输出：16
示例 4：

输入：arr = [100,100,99,99]
输出：4
示例 5：

输入：arr = [7]
输出：1

解题思路

先计算前缀和，可以发现规律：
任意两个前缀和作差就是一个子数组的和，这个和到底是鸡还是偶取决于选出的两个前缀和的奇偶性。当两个前缀和一奇一偶时，减出的子数组和就是奇数。所以把前缀和划分为奇数一拨，以及偶数一拨。
这两拨的组合个数 + 奇数前缀和个数=子数组和为奇数的个数
上面之所以要加上奇数前缀和个数，是因为单独的奇数前缀和本身就是子数组和。
代码如下：

class Solution {
    public int numOfSubarrays(int[] arr) {
        long sum = 0;
        long even = 0;
        long odd = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum %2 != 0){
                odd++;
            }else {
                even++;
            }
        }

        return (int)((odd + odd * even) % (1000000007));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17