和为奇数的子数组数目

记牢这条主线:子数组和为奇,就是它两端的前缀和奇偶不同。于是只用两个桶记下偶前缀、奇前缀各出现多少次,扫到一个新前缀就往答案里加上相反奇偶那个桶的个数。下面每一帧都在套这条线。

阶段一 · 起点是一个偶前缀：开扫之前先摆好起点。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);只需奇偶两个桶因为判定只看奇偶差;取模只为防溢出,不影响计数。