和为奇数的子数组数目 图解题解

和为奇数的子数组数目，到底在数什么

给一个整数数组 arr，子数组指数组里一段连续的元素。要数出有多少个子数组里所有数加起来是奇数，结果对 10 的 9 次方加 7 取余（取余即只保留除以这个大质数后的余数，防溢出）。题面 arr = [1, 3, 5] 的答案是 4，四段奇和子数组是 [1]、[1, 3, 5]、[3]、[5]。

逐个子数组求和为什么会超时

长度 n 的数组里有大约 n²／2 个子数组，arr 最长十万，逐段求和再判断奇偶就是上百亿次加法，根本跑不完。大 O 记号 O(n²)（描述规模变大时操作数怎么涨）就是超时红线。慢的根子是每段和都从头重加，相邻两段只差一个数却各算一遍。

子数组和的奇偶，怎么变成两端前缀的奇偶

引入前缀和：pre[i] 是数组前 i 个数的累加和（从头一直加到第 i 个位置的总和），约定 pre[0] = 0 表示什么都不加。任意一段子数组的和，等于右端前缀和减左端前缀和。它是奇数，当且仅当两个前缀一奇一偶；同奇或同偶相减必为偶。

于是不用管前缀和具体多少，只盯它奇偶。数奇和子数组，就变成数「有多少对前缀奇偶不同」。

当前前缀是奇，为什么要去数偶前缀

从左往右扫，一边累加前缀和 s，一边用两个桶记账：cnt[0] 是见过的偶前缀个数、cnt[1] 是奇前缀个数。桶初始为 cnt = [1, 0]，那个 1 记的是空前缀 pre[0] = 0（0 是偶）。

每加进一个新元素、得到新前缀 s，要数以这里结尾的奇和子数组，就看它能跟左边哪些前缀配成一奇一偶。s 是奇就加偶前缀个数 cnt[0]，s 是偶就加 cnt[1]——配的永远是相反奇偶那个桶，奇配奇、偶配偶相减得偶、不算。数完把当前前缀按自己的奇偶记进对应桶，留给右边配对。每次累加都对 10 的 9 次方加 7 取余。

拿 [1, 3, 5] 亲手把两个桶数一遍

起手 cnt = [1, 0]、s = 0、ans = 0。加 1：s = 1 奇，加偶前缀 cnt[0] = 1，ans 变 1，奇前缀记进桶得 cnt = [1, 1]。加 3：s = 4 偶，加奇前缀 cnt[1] = 1，ans 变 2，偶前缀记进桶得 cnt = [2, 1]。加 5：s = 9 奇，加偶前缀 cnt[0] = 2，ans 加 2 变 4，记桶后 cnt = [2, 2]。

扫完 ans = 4，和题面答案对上。三次分别加 1、1、2，正好数清 [1]、[3]、[5] 和整段 [1, 3, 5] 这四段。

少给偶前缀记那个 1，答案为什么会凭空少一截

一趟扫到底，每个元素只做常数次加法、查桶、累加，时间 O(n)（n 是数组长度）；只用长度 2 的桶和 s、ans 两个变量，空间 O(1)（占用恒定，与 n 无关）。

初始 cnt = [1, 0] 里那个 1 别当可有可无：它记的是空前缀 pre[0]，省掉后从下标 0 开头的奇和子数组会因左端配不上而漏掉，连 [1] 都数不到。方向也别搞反——奇前缀加偶桶、偶前缀加奇桶，写成加同奇偶那个桶，数出来全是偶和子数组。取模同样漏不得，不改变哪段被数到，但十万级计数不取余会溢出。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        cnt = [1, 0]
        ans = s = 0
        for x in arr:
            s += x
            ans = (ans + cnt[s & 1 ^ 1]) % mod
            cnt[s & 1] += 1
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int mod = 1e9 + 7;
        int cnt[2] = {1, 0};
        int ans = 0, s = 0;
        for (int x : arr) {
            s += x;
            ans = (ans + cnt[s & 1 ^ 1]) % mod;
            ++cnt[s & 1];
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int numOfSubarrays(int[] arr) {
        final int mod = (int) 1e9 + 7;
        int[] cnt = {1, 0};
        int ans = 0, s = 0;
        for (int x : arr) {
            s += x;
            ans = (ans + cnt[s & 1 ^ 1]) % mod;
            ++cnt[s & 1];
        }
        return ans;
    }
}