【力扣刷题】和为奇数的子数组数目（前缀和）

· 2021-11-15 · # Algorithm

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;
    }
};