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

这道题到底在问什么

输入

arr = [1,3,5]

输出

4(奇和子数组 [1] [1,3,5] [3] [5])

输入

arr = [2,4,6]

输出

0(全是偶数,任何一段和都是偶)

输入

arr = [1,2,3,4,5,6,7]

输出

16

先想最直接的笨办法

把每一步往答案里加的数串起来看:依次加了 1、1、2、2、3,正好等于 9。拿暴力数一遍核对,arr = [1, 2, 3, 4, 5] 里和为奇数的子数组确实有 9 个,比如 [1]、[2,3]、[5]、整段 [1,2,3,4,5] 等等。一遍线性扫,只靠两个计数桶就把它们全数清了。（动画第 23 步）

最优解：一步一步想明白

1. 3记牢这条主线:子数组和为奇,就是它两端的前缀和奇偶不同。于是只用两个桶记下偶前缀、奇前缀各出现多少次,扫到一个新前缀就往答案里加上相反奇偶那个桶的个数。下面每一帧都在套这条线。
2. 4开扫之前先摆好起点。pre[0] 表示前 0 个数的和,也就是什么都不加,值是 0,0 是偶数,所以面板里偶前缀个数先记成 1,奇前缀是 0,答案 ans 是 0。这一个空前缀很关键:正是它让那些从下标 0 开头的子数组也能被正确配对,后面会看到它发挥作用。
3. 5先拿一个具体子数组体会转化。取 arr 开头两个数 1 和 2,这段的和是 3,是奇数。从前缀和看,这段和等于 pre[2] 减 pre[0],也就是前两个数的和 3 减去 0。pre[0] 是偶、pre[2] 是奇,一个偶一个奇,相减得到奇数。反过来,如果两端前缀奇偶相同,相减一定是偶。这就是为什么我们只盯奇偶、不在乎具体数值。
4. 6再看一个反例做对比。取开头三个数 1、2、3,这段的和是 6,是偶数。它等于 pre[3] 减 pre[0],也就是 6 减 0。pre[0] 和 pre[3] 都是偶,奇偶相同,相减得到偶数,这种就不算我们要的奇和子数组。两个例子合起来记住一句话:两端前缀奇偶不同才是奇和,奇偶相同就是偶和。配对时永远去找相反奇偶的前缀。
5. 7扫到下标 0 的元素 1,把它加进前缀和:s 从 0 变成 1。这是包含前 1 个数的前缀,它是奇数。注意加进来的 1 是奇数,会把前缀的奇偶翻一下。下一帧用这个奇偶去面板里配对。
6. 8当前这个前缀是奇。要让一段子数组以下标 0 结尾且和为奇,它的左端那个前缀必须是相反的偶。面板里偶前缀现在有 1 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 1。ans 从 0 变成 1。
7. 9配完别忘了把当前这个奇前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 奇前缀个数变成 1。这一轮结束:偶前缀 1 个、奇前缀 1 个,答案累计 1。继续扫下一个元素。
8. 10扫到下标 1 的元素 2,把它加进前缀和:s 从 1 变成 3。这是包含前 2 个数的前缀,它是奇数。注意加进来的 2 是偶数,前缀的奇偶保持不变。下一帧用这个奇偶去面板里配对。
9. 11当前这个前缀是奇。要让一段子数组以下标 1 结尾且和为奇,它的左端那个前缀必须是相反的偶。面板里偶前缀现在有 1 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 1。ans 从 1 变成 2。
10. 12配完别忘了把当前这个奇前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 奇前缀个数变成 2。这一轮结束:偶前缀 1 个、奇前缀 2 个,答案累计 2。继续扫下一个元素。
11. 13扫到下标 2 的元素 3,把它加进前缀和:s 从 3 变成 6。这是包含前 3 个数的前缀,它是偶数。注意加进来的 3 是奇数,会把前缀的奇偶翻一下。下一帧用这个奇偶去面板里配对。
12. 14当前这个前缀是偶。要让一段子数组以下标 2 结尾且和为奇,它的左端那个前缀必须是相反的奇。面板里奇前缀现在有 2 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 2。ans 从 2 变成 4。
13. 15配完别忘了把当前这个偶前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 偶前缀个数变成 2。这一轮结束:偶前缀 2 个、奇前缀 2 个,答案累计 4。继续扫下一个元素。
14. 16扫到下标 3 的元素 4,把它加进前缀和:s 从 6 变成 10。这是包含前 4 个数的前缀,它是偶数。注意加进来的 4 是偶数,前缀的奇偶保持不变。下一帧用这个奇偶去面板里配对。
15. 17当前这个前缀是偶。要让一段子数组以下标 3 结尾且和为奇,它的左端那个前缀必须是相反的奇。面板里奇前缀现在有 2 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 2。ans 从 4 变成 6。
16. 18配完别忘了把当前这个偶前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 偶前缀个数变成 3。这一轮结束:偶前缀 3 个、奇前缀 2 个,答案累计 6。继续扫下一个元素。
17. 19扫到下标 4 的元素 5,把它加进前缀和:s 从 10 变成 15。这是包含前 5 个数的前缀,它是奇数。注意加进来的 5 是奇数,会把前缀的奇偶翻一下。下一帧用这个奇偶去面板里配对。
18. 20当前这个前缀是奇。要让一段子数组以下标 4 结尾且和为奇,它的左端那个前缀必须是相反的偶。面板里偶前缀现在有 3 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 3。ans 从 6 变成 9。
19. 21配完别忘了把当前这个奇前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 奇前缀个数变成 3。这一轮结束:偶前缀 3 个、奇前缀 3 个,答案累计 9。数组已经扫完,进入收束回看。
20. 22整条 arr 扫完。把六个前缀的奇偶排出来看:pre[0] 到 pre[5] 依次是偶、奇、奇、偶、偶、奇,偶有 3 个、奇有 3 个。整个过程我们从没回头,只是一边累加前缀和、一边维护两个计数桶,答案就一点点攒到了 9。
21. 23把每一步往答案里加的数串起来看:依次加了 1、1、2、2、3,正好等于 9。拿暴力数一遍核对,arr = [1, 2, 3, 4, 5] 里和为奇数的子数组确实有 9 个,比如 [1]、[2,3]、[5]、整段 [1,2,3,4,5] 等等。一遍线性扫,只靠两个计数桶就把它们全数清了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

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

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

复杂度

面试官可能追问