算法

(数学) $O(n)$

注意到偶数-奇数=奇数，奇数-偶数=奇数，于是我们可以用前缀和来处理：
遍历数组中的每个元素，计算当前的前缀和，如果前缀和是偶数，那么就要找和为奇数的数组，把答案增加$odd$，同时把$even+1$，否则我们需要找之前和为偶数的数组，把答案增加$even$，同时把$odd+1$。

其中：odd为和为奇数的数组数目，even为和为偶数的数组数目

C++ 代码

class Solution {
public:
    const int MOD = 1e9 + 7;
    int numOfSubarrays(vector<int>& arr) {
        int odd = 0, even = 1; // 空数组的和为0，所以odd = 0, even = 1
        long long ans = 0;
        int sum = 0;
        for (int x : arr) {
            sum += x;
            if (sum % 2 == 0) {
                ans += odd;
                ++even;
            }
            else {
                ans += even;
                ++odd;
            }
        }
        return ans % MOD;
    }
};