【力扣刷题】和为奇数的子数组数目（前缀和）
1524. 和为奇数的子数组数目：给你一个整数数组
arr。请你返回和为 奇数 的子数组数目。
由于答案可能会很大，请你将结果对10^9 + 7取余后返回。
以下实例为小马智行（pony.ai）二面coding面试题。
输入：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 。
这里总结一下前缀和的算法思想。给定一个int arr[]数组，我们要计算第i项及以前的和, sum[i]表示从下标0到下标i的和，那么sum[i] = sum[i - 1] + arr[i]，这里的前缀和就是sum[i - 1]。也就是所记录的前缀和应该是[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]...这个样子。
参考yuyangxianyi的题解，如果当前和为奇数的话，例如[1, 2, 3, 4, 5], 计算到第5个数时和为奇数，我们只要减去前缀和为偶数的即可，例如减去[1, 2, 3], 这样这个序列就剩下[4, 5]是奇数，也是新增的项，还可以减去[1, 2, 3, 4], 剩下[5], 也是新增的一项，本质为：奇数 - 偶数 = 奇数，意思就是说，有几个偶前缀和，就新增几项。相反的，如果当前和为偶数，只需要减去所有奇数的前缀和，即为新增的数目，本质为：偶数 - 奇数 = 奇数。最后把当前的和是奇数，令前缀和为奇数的++, 反之亦然。
起初前缀和是偶数值为1是因为可以理解为默认一个0的存在。
class Solution {
public:
typedef long long ll;
#define mod 1000000007
int numOfSubarrays(vector<int>& arr) {
//前缀和为0到i的arr和
ll even_pre_sum = 1; // 可以理解为0 + pre_sum
ll odd_pre_sum = 0;
ll sum = 0;
int ans = 0;
for (int i = 0; i < arr.size(); i++) {
sum += arr[i];
if (sum % 2) {//arr和为奇数
//如果当前和为奇数，要减去前缀和为偶数的即可
ans += even_pre_sum; //即有几个偶前缀和，就新增几项
odd_pre_sum++;
} else {
ans += odd_pre_sum;
even_pre_sum++;
}
ans %= mod;
}
return ans;
}
};