题目描述
思路解析
一句话答案：LeetCode 1524 和为奇数的子数组数目：子数组和为奇等价于两端前缀和奇偶不同，维护奇、偶前缀个数两桶，每步把答案加相反桶再取模，时间 O(n)、空间 O(1)。
和为奇数的子数组数目，到底在数什么
给一个整数数组 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] 都数不到。方向也别搞反——奇前缀加偶桶、偶前缀加奇桶，写成加同奇偶那个桶，数出来全是偶和子数组。取模同样漏不得，不改变哪段被数到，但十万级计数不取余会溢出。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这条主线:子数组和为奇,就是它两端的前缀和奇偶不同。于是只用两个桶记下偶前缀、奇前缀各出现多少次,扫到一个新前缀就往答案里加上相反奇偶那个桶的个数。下面每一帧都在套这条线。
阶段一 · 起点是一个偶前缀：开扫之前先摆好起点。pre[0] 表示前 0 个数的和,也就是什么都不加,值是 0,0 是偶数,所以面板里偶前缀个数先记成 1,奇前缀是 0,答案 ans 是 0。这一个空前缀很关键:正是它让那些从下标 0 开头的子数组也能被正确配对,后面会看到它发挥作用。
阶段一 · 先体会奇偶不同：先拿一个具体子数组体会转化。取 arr 开头两个数 1 和 2,这段的和是 3,是奇数。从前缀和看,这段和等于 pre[2] 减 pre[0],也就是前两个数的和 3 减去 0。pre[0] 是偶、pre[2] 是奇,一个偶一个奇,相减得到奇数。反过来,如果两端前缀奇偶相同,相减一定是偶。这就是为什么我们只盯奇偶、不在乎具体数值。
阶段一 · 再看一个反例：再看一个反例做对比。取开头三个数 1、2、3,这段的和是 6,是偶数。它等于 pre[3] 减 pre[0],也就是 6 减 0。pre[0] 和 pre[3] 都是偶,奇偶相同,相减得到偶数,这种就不算我们要的奇和子数组。两个例子合起来记住一句话:两端前缀奇偶不同才是奇和,奇偶相同就是偶和。配对时永远去找相反奇偶的前缀。
元素 0 · 算前缀和：扫到下标 0 的元素 1,把它加进前缀和:s 从 0 变成 1。这是包含前 1 个数的前缀,它是奇数。注意加进来的 1 是奇数,会把前缀的奇偶翻一下。下一帧用这个奇偶去面板里配对。
元素 0 · 累加答案：当前这个前缀是奇。要让一段子数组以下标 0 结尾且和为奇,它的左端那个前缀必须是相反的偶。面板里偶前缀现在有 1 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 1。ans 从 0 变成 1。
元素 0 · 当前前缀进桶：配完别忘了把当前这个奇前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 奇前缀个数变成 1。这一轮结束:偶前缀 1 个、奇前缀 1 个,答案累计 1。继续扫下一个元素。
元素 1 · 算前缀和：扫到下标 1 的元素 2,把它加进前缀和:s 从 1 变成 3。这是包含前 2 个数的前缀,它是奇数。注意加进来的 2 是偶数,前缀的奇偶保持不变。下一帧用这个奇偶去面板里配对。
元素 1 · 累加答案：当前这个前缀是奇。要让一段子数组以下标 1 结尾且和为奇,它的左端那个前缀必须是相反的偶。面板里偶前缀现在有 1 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 1。ans 从 1 变成 2。
元素 1 · 当前前缀进桶：配完别忘了把当前这个奇前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 奇前缀个数变成 2。这一轮结束:偶前缀 1 个、奇前缀 2 个,答案累计 2。继续扫下一个元素。
元素 2 · 算前缀和：扫到下标 2 的元素 3,把它加进前缀和:s 从 3 变成 6。这是包含前 3 个数的前缀,它是偶数。注意加进来的 3 是奇数,会把前缀的奇偶翻一下。下一帧用这个奇偶去面板里配对。
元素 2 · 累加答案：当前这个前缀是偶。要让一段子数组以下标 2 结尾且和为奇,它的左端那个前缀必须是相反的奇。面板里奇前缀现在有 2 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 2。ans 从 2 变成 4。
元素 2 · 当前前缀进桶：配完别忘了把当前这个偶前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 偶前缀个数变成 2。这一轮结束:偶前缀 2 个、奇前缀 2 个,答案累计 4。继续扫下一个元素。
元素 3 · 算前缀和：扫到下标 3 的元素 4,把它加进前缀和:s 从 6 变成 10。这是包含前 4 个数的前缀,它是偶数。注意加进来的 4 是偶数,前缀的奇偶保持不变。下一帧用这个奇偶去面板里配对。
元素 3 · 累加答案：当前这个前缀是偶。要让一段子数组以下标 3 结尾且和为奇,它的左端那个前缀必须是相反的奇。面板里奇前缀现在有 2 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 2。ans 从 4 变成 6。
元素 3 · 当前前缀进桶：配完别忘了把当前这个偶前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 偶前缀个数变成 3。这一轮结束:偶前缀 3 个、奇前缀 2 个,答案累计 6。继续扫下一个元素。
元素 4 · 算前缀和：扫到下标 4 的元素 5,把它加进前缀和:s 从 10 变成 15。这是包含前 5 个数的前缀,它是奇数。注意加进来的 5 是奇数,会把前缀的奇偶翻一下。下一帧用这个奇偶去面板里配对。
元素 4 · 累加答案：当前这个前缀是奇。要让一段子数组以下标 4 结尾且和为奇,它的左端那个前缀必须是相反的偶。面板里偶前缀现在有 3 个,每一个都能和当前前缀配成一段奇和子数组,所以答案加上 3。ans 从 6 变成 9。
元素 4 · 当前前缀进桶：配完别忘了把当前这个奇前缀也记进面板,因为后面更靠右的前缀还要拿它来配对。现在 奇前缀个数变成 3。这一轮结束:偶前缀 3 个、奇前缀 3 个,答案累计 9。数组已经扫完,进入收束回看。
收束 · 奇偶序列回看：整条 arr 扫完。把六个前缀的奇偶排出来看:pre[0] 到 pre[5] 依次是偶、奇、奇、偶、偶、奇,偶有 3 个、奇有 3 个。整个过程我们从没回头,只是一边累加前缀和、一边维护两个计数桶,答案就一点点攒到了 9。
完成 · 答案 9：把每一步往答案里加的数串起来看:依次加了 1、1、2、2、3,正好等于 9。拿暴力数一遍核对,arr = [1, 2, 3, 4, 5] 里和为奇数的子数组确实有 9 个,比如 [1]、[2,3]、[5]、整段 [1,2,3,4,5] 等等。一遍线性扫,只靠两个计数桶就把它们全数清了。
边界:单个奇数给 1、单个偶数给 0、整列偶数答案 0(前缀一直偶,相反奇桶始终空)。
面试重点:朴素枚举 O(n²) 到前缀和奇偶计数 O(n);只需奇偶两个桶因为判定只看奇偶差;取模只为防溢出,不影响计数。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n)，n 是 arr 长度。只从头到尾扫一遍,每个元素做的都是常数次加法、查桶、累加,合计线性
- 空间：O(1)，只用长度为 2 的计数桶 cnt 和几个标量 s、ans,峰值占用是常数,与 n 无关。动画里画的奇偶序列是帮助理解的教学辅助,不是算法必需
易错点
面试追问把动画讲成自己的话
追问最朴素的做法是什么,为什么慢?
追问为什么只记奇偶两个桶就够,不用记每个前缀和的具体值?
追问取模会不会影响计数的正确性?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符串的好分割数目
LeetCode 1525 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题