题目描述

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

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

样例

输入：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。

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

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

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

限制

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 100

算法

(前缀和) $O(n)$

1. 对于以 $i$ 结尾的区间，我们统计 $j$ 的个数，满足 $sum(i) - sum(j - 1)$ 为奇数，其中 $sum(i)$ 为前缀和。
2. 如果 $sum(i)$ 为奇数，则我们只需要知道有多少个 $j$，满足 $sum(j - 1)$ 是偶数。反之亦然，所以我们可以在过程中统计奇数前缀和与偶数前缀和的个数。
3. 注意，初始时，偶数前缀和的个数为 1。

时间复杂度

• 遍历一次数组，每个位置仅需要常数的时间统计答案，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int mod = 1000000007;

        int odd = 0, even = 1;
        int sum = 0, ans = 0;

        for (int x : arr) {
            sum += x;
            if (sum & 1) {
                ans = (ans + even) % mod;
                odd++;
            } else {
                ans = (ans + odd) % mod;
                even++;
            }
        }

        return ans;
    }
};