---

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

• 标签：数组、数学、动态规划、前缀和
• 难度：中等

题目链接

• 1524. 和为奇数的子数组数目 - 力扣

题目大意

描述：给定一个整数数组 $arr$。

要求：返回和为奇数的子数组数目。结果对 $10^9 + 7$ 取模。

说明：

• $1 \le arr.length \le 10^5$。
• $1 \le arr[i] \le 100$。

示例：

• 示例 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

• 示例 2：

输入：
输出：

解题思路

思路 1：前缀和 + 奇偶计数

1. 核心思想

子数组 $arr[l..r]$ 的和的奇偶性 = $(prefix[r+1] - prefix[l]) \% 2$，其中 $prefix[i]$ 为前 $i$ 个元素的和的奇偶性。

要使子数组和为奇数，需要 $prefix[r+1]$ 和 $prefix[l]$ 的奇偶性不同。

遍历时，维护奇偶前缀和计数。对于当前位置 $i$：

• 如果 $prefix[i]$ 为偶数，与之前所有奇数前缀和的位置都能形成奇数子数组。
• 如果 $prefix[i]$ 为奇数，与之前所有偶数前缀和的位置都能形成奇数子数组。

2. 具体步骤

第 1 步：初始化 $cnt[0] = 1$（空前缀和为偶数），$cnt[1] = 0$。$prefix = 0$，$ans = 0$。

第 2 步：遍历每个 $x$：

• $prefix = (prefix + x) \% 2$。
• $ans = (ans + cnt[1 - prefix]) \% MOD$。
• $cnt[prefix] += 1$。

第 3 步：返回 $ans$。

3. 举例说明

以 $arr = [1,3,5]$ 为例：

• $i=0$：$x=1$，$prefix=1$（奇数），之前偶数子数组数 $cnt[0]=1$，$ans=1$。$cnt[1]=1$。
• $i=1$：$x=3$，$prefix=0$（偶数），之前奇数子数组数 $cnt[1]=1$，$ans=2$。$cnt[0]=2$。
• $i=2$：$x=5$，$prefix=1$（奇数），之前偶数子数组数 $cnt[0]=2$，$ans=4$。

返回 $4$。

子数组：$[1], [3], [5], [1,3], [3,5], [1,3,5]$。
和为奇数的：$[1], [3], [5], [1,3,5]$，$4$ 个。

思路 1：代码

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 10 ** 9 + 7
        cnt = [1, 0]  # cnt[0]=偶数前缀和个数, cnt[1]=奇数前缀和个数
        prefix = 0
        ans = 0
        for x in arr:
            prefix = (prefix + x) & 1
            ans = (ans + cnt[1 - prefix]) % MOD
            cnt[prefix] += 1
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。