1524.png

求和为奇数的子数组数组，如果直接暴力枚举显示不可取的，数据范围比较大。

涉及到的数组和的问题，通常第一想法就是考虑能不能用前缀和去处理一下。

对应到这题中，正好可以用前缀和处理，在处理每个位置的前缀和时，我们可以动态的维护一种长度为2的数组，这个数组用于统计 【截止到当前位置】和为奇数或者偶数的数量

数组： arr = [1, 3, 5]
前缀和为： sum = [0 , 1, 4, 9]
统计数组结果分别为： [1, 0] [1, 1] [2, 1] [2, 2]

这个统计数组有何用？
用于实现不同的组合的累加

以统计数组的第三个状态：即前缀和为4时，对应的统计状态[2, 1]，表示目前位置有2个和为偶数，一个和为奇数。
接下来利用统计数组的中的奇或偶的个数进行不同的【组合】，遍历到 前缀和4时，4是偶数，要想变成奇数，那么就必须与奇数相加才可以，因为 4 可以和【任意一个】奇数相组合。

class Solution {
    int mod = (int)1e9 + 7;
    public int numOfSubarrays(int[] arr) {
        int[] cnt = new int[] {1, 0};
        int n = arr.length;
        long r = 0;
        for(int i = 0, sum = 0; i < n; i++) {
            ++cnt[sum ^= arr[i] & 1];
            r += cnt[sum ^ 1];
        }
        return (int) (r % mod);
    }
}