1524. 和为奇数的子数组数目 Medium

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

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

示例 1:
输入：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 。

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

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

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

示例 5:
输入：arr = [7]
输出：1

解题思路

输入：一个整数数组 arr

输出：返回和为 奇数 的子数组数目

本题属于一维前缀和问题。

我们首先要知道:

• 奇数 + 奇数 = 偶数
• 奇数 + 偶数 = 奇数

所以想要得到合为奇数的子数组，我们可以通过前缀和 preSum 得出之前出现过多少奇数的和

• 当 preSum 为奇数时，只可能是 奇数 = 奇数 + 偶数 组合 奇数子数组数量 = 偶数前缀和个数
• 当 preSum 为偶数时，不论是 奇数 + 奇数 或者是 偶数 + 偶数，奇数子数组数量 = 奇数前缀和个数

代码实现

python

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # 初始化：奇数前缀和的个数为 0，偶数前缀和为 1（表示前缀和为 0 的初始情况）
        odd = 0
        even = 1  # 和为 0 是偶数，所以从 1 开始
        ans = 0
        mod = 10**9 + 7  # 模数
        preSum = 0       # 当前前缀和

        # 遍历整个数组
        for num in arr:
            preSum += num

            # 当前前缀和为偶数，则本轮可以与之前所有奇数前缀配对，形成奇数子数组
            if preSum % 2 == 0:
                ans += odd
                even += 1  # 当前是偶数前缀，统计加一
            else:
                ans += even
                odd += 1   # 当前是奇数前缀，统计加一
        
        return ans % mod

javascript

/**
 * @param {number[]} arr
 * @return {number}
 */
var numOfSubarrays = function(arr) {
    let ans = 0;
    let odd = 0;
    let even = 1;
    let preSum = 0;
    const mod = 10 ** 9 + 7;

    for (let num of arr) {
        preSum += num;

        if (preSum % 2 == 0) {
            ans += odd;
            even ++;
        } else {
            ans += even;
            odd ++;
        }
    }

    return ans % mod;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

1524 国际版

1524 中文版