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

2021-10-13 HGNULB 约 8 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

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

题意分析

给定一个正整数数组，要统计有多少个连续子数组的元素之和是奇数，结果对 $10^9 + 7$ 取模。注意统计的是「子数组的个数」，不是「和的总量」，也不要求把这些子数组列出来。

数组长度可以到 $10^5$，而子数组的数量是 $O(n^2)$ 量级，光是枚举出所有子数组就已经超时了。这个规模差距说明答案必须在一次线性扫描里累加出来，每个下标只能被处理常数次。

题目要求取模，这是在提示答案会溢出 32 位。取模只是收尾动作，不改变任何计数逻辑，但累加过程中如果用 int 直接相加会先溢出再取模，结果就错了。

元素值域是 1 到 100 的正整数，全为正数意味着前缀和严格递增，但本题只关心奇偶性，所以这个单调性并不能用来做双指针，真正有用的信息是「和的奇偶性只由参与相加的奇数个数决定」。

边界上要注意长度为 1 的子数组也算数，数组只有一个元素时答案是 0 或 1；另外单个元素本身就可能是奇数，不能只考虑长度大于 1 的情况。

解法：前缀和奇偶计数

核心思路

最直接的写法是双重循环：外层固定左端点，内层向右扩展并维护累加和，每次判断一次奇偶。这样能得到正确答案，但要做 $O(n^2)$ 次加法，$10^5$ 的规模下必然超时。

瓶颈在于同一段区间的和被反复重算，而且每次都是拿到完整数值后才判断奇偶——数值本身根本不重要，重要的只有它模 2 的结果。

沿着这个思路观察：记 pre[i] 为前 i 个元素之和，那么以 j 结尾、从 i 开始的子数组和就是 pre[j+1] - pre[i]。这个差是奇数，当且仅当 pre[j+1] 与 pre[i] 一个是奇数、一个是偶数。于是「统计和为奇数的子数组」就等价于「统计前缀和序列里奇偶性相异的下标对」，而下标对的先后顺序天然由扫描方向保证。

再进一步，判定只用到奇偶两种取值，所以完全不必存下每个前缀和，只要记住「到目前为止出现过多少个偶前缀、多少个奇前缀」这两个计数器。

由此确定不变量：扫描到第 j 个元素并更新完当前前缀奇偶 sum 之后，evenCount 与 oddCount 分别表示下标严格小于当前前缀位置的那些前缀中，偶前缀与奇前缀的个数；answer 表示所有右端点落在 j 及其之前的、和为奇数的子数组总数。空数组对应的前缀和为 0，是一个合法的偶前缀，必须在扫描开始前就计入 evenCount，否则所有从下标 0 起头的子数组都会被漏掉。

解题步骤

把 evenCount 初始化为 1、oddCount 初始化为 0。这一步等价于把「空前缀」这个偶前缀先放进计数器，因为任何以下标 0 开头的子数组，都要拿空前缀去做减法配对。

用一个 sum 变量维护当前前缀和的奇偶，每读入一个元素就执行 sum = (sum + num) % 2。只保留模 2 的余数而不是真实和，是为了从根上避免溢出，同时把状态压成两种取值。

当前 sum 为奇数时，把 evenCount 累加进答案。因为「奇 − 偶 = 奇」，此前每一个偶前缀都能和当前位置组成一个合法子数组，累加的是数量而不是 1。

当前 sum 为偶数时，把 oddCount 累加进答案，理由对称：「偶 − 奇 = 奇」。

累加完答案之后，再把当前前缀按其奇偶记进对应的计数器，使计数器始终只表示严格更早的前缀。本题查询的是相反奇偶，先记当前桶再查另一桶不会改变数值结果，但「先查后记」与状态定义一致，也便于迁移到同余配对问题。

答案用 long（Go 里每步取模）累加并及时对 $10^9 + 7$ 取模。子数组总数最大约 $5 \times 10^9$，超过了 int 上限，先溢出再取模会得到负数。

以 arr = [1, 3, 5] 走一遍：初始 evenCount = 1、oddCount = 0、sum = 0、answer = 0。读入 1，sum 变成 1 是奇前缀，累加 evenCount = 1，answer = 1，随后 oddCount 变成 1——这一步对应子数组 [1]。读入 3，sum 变成 (1 + 3) % 2 = 0 是偶前缀，累加 oddCount = 1，answer = 2，随后 evenCount 变成 2——这一步对应子数组 [3]，注意 [1,3] 和为 4 并未被计入。读入 5，sum 变成 (0 + 5) % 2 = 1，此前两个偶前缀分别位于开头和元素 3 之后，因此新增的是 [1,3,5] 与 [5]，answer 变成 4。扫描结束返回 4，与手工枚举一致。

代码实现

// 遍历到当前位置时，只需要知道之前出现过多少个偶前缀和奇前缀，不需要保存具体前缀值。
class Solution {
    public int numOfSubarrays(int[] arr) {
        int mod = 1000000007;
        int evenCount = 1;
        int oddCount = 0;
        int sum = 0;
        long answer = 0;

        for (int num : arr) {
            sum = (sum + num) % 2;
            if (sum == 1) {
                answer += evenCount;
                oddCount++;
            } else {
                answer += oddCount;
                evenCount++;
            }
            answer %= mod;
        }

        return (int) answer;
    }
}

// 遍历到当前位置时，只需要知道之前出现过多少个偶前缀和奇前缀，不需要保存具体前缀值。
func numOfSubarrays(arr []int) int {
	const mod = 1000000007
	evenCount := 1
	oddCount := 0
	sum := 0
	answer := 0

	for _, num := range arr {
		sum = (sum + num) % 2
		if sum == 1 {
			answer = (answer + evenCount) % mod
			oddCount++
		} else {
			answer = (answer + oddCount) % mod
			evenCount++
		}
	}

	return answer
}

复杂度分析

时间复杂度：$O(n)$。数组只被完整扫描一次，每个元素上做的都是一次取模加法、一次分支判断和两次计数更新，全是常数时间操作。

空间复杂度：$O(1)$。全程只用了 evenCount、oddCount、sum、answer 四个标量，不随输入规模增长，也没有开任何前缀数组或哈希表。

关键点总结

「子数组和满足某性质」的计数题，先把它翻译成「两个前缀和之差满足某性质」，再翻译成「前缀和的某个特征值配对」，是一条通用的降维路径，从 $O(n^2)$ 直接掉到 $O(n)$。

当判定只依赖前缀和的某个有限特征（这里是模 2，别的题里是模 K、是 0/1 计数差），哈希表就可以退化成固定大小的计数数组，空间从 $O(n)$ 降到 $O(1)$。

空前缀必须作为初始状态预置进计数器，否则所有从下标 0 开始的子数组都会丢失，这是前缀和配对类题目最高频的漏点。

「先查询后写入」是这类扫描的固定节拍，保证配对的两个前缀严格来自不同位置，避免自己和自己组成空区间。

计数结果的量级要单独估：$n$ 到 $10^5$ 时子数组总数是 $10^{10}$ 量级，累加变量必须用 64 位，取模只能在加法之后立刻做。

面试视角：这题的正确开场不是写代码，而是先说出「和为奇 ⟺ 两个前缀和奇偶不同」这句等价转化，把 $O(n^2)$ 枚举压掉。说完这句面试官基本就认可了，剩下的编码只是把两个计数器写对。常见追问是「改成求和能被 K 整除的子数组怎么办」，答案是把两个计数器换成长度为 K 的余数计数数组，同余的配对而不是相异的配对，负数还要先修正到非负余数。

易错点总结

错误写法：evenCount 初始化为 0，不预置空前缀。用例 arr = [1] → 读入 1 后 sum 为奇，累加 evenCount = 0，返回 0，而正确答案是 1。

错误写法：当前前缀为奇数时，累加答案后却递增 evenCount。用例 arr = [1,1] 中第一次把奇前缀记错桶，第二个前缀变偶时找不到此前的奇前缀，只返回 1；正确答案是 2。

错误写法：sum 直接累加真实和而不取模 2。用例 arr 为 $10^5$ 个 100 → 真实前缀和达到 $10^7$ 尚不溢出，但若元素上界更大就会溢出成负数，sum == 1 的判断随之失效；同时负数取模在 Java 里得到 -1，永远匹配不上分支。

错误写法：answer 用 int 累加，最后才取模。用例长度 $10^5$ 的全奇数数组 → 中间结果超过 $2^{31}$ 溢出为负数，返回负值。

错误写法：当前前缀为奇时去累加 oddCount（配对方向写反）。用例 arr = [1, 3, 5] → 依次累加 0、2、1 得到 3，正确答案是 4。

错误写法：把答案理解成「和为奇数的子数组之和」，累加的是元素值而不是计数。用例 arr = [1, 3, 5] → 返回 1 + 3 + 5 + 9 = 18，正确答案是 4。

错误写法：认为只有奇数元素能贡献答案，遇到偶数直接 continue 不更新 sum。用例 arr = [2, 1] → 跳过 2 后前缀奇偶错位，子数组 [2,1] 被漏掉，返回 1，正确答案是 2。

错误写法：取模写成 answer % mod 但没有把结果赋回 answer。用例长度 $10^5$ 的数组 → 取模语句成为空操作，answer 一路增长到溢出。

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	配对条件从奇偶相异变成差值恰为 K，计数器必须换回哈希表
974. 和可被 K 整除的子数组	中等	模数从 2 推广到 K，且要处理负数取模修正到非负余数
523. 连续的子数组和	中等	同余判定改为存首次出现下标，还要满足长度至少为 2 的限制
525. 连续数组	中等	把 0 映射为 -1 后求最长而非计数，哈希表存的是最早下标
930. 和相同的二元子数组	中等	元素非负使前缀单调，除前缀和外还能用滑动窗口做差解
1590. 使数组和能被 P 整除	中等	反过来找最短的待删子数组，目标余数由总和决定
1010. 总持续时间可被 60 整除的歌曲	中等	配对对象是元素本身而非前缀和，且要求余数互补而不是相同