LeetCode 1524. 和为奇数的子数组数目
题目描述
题意分析
统计有多少个非空连续子数组的元素和为奇数，结果对 $10^9+7$ 取模。不同起止位置分别计数，即使内容相同也属于不同子数组。
只关心总和的奇偶，不要求子数组只包含奇数。多个奇数相加可能变成偶数，偶数元素也可以出现在合法子数组中。
解法：前缀和奇偶计数
核心思路
[!blue]
子数组和等于右侧前缀和减去左端之前的前缀和。两个数的差为奇数，当且仅当它们奇偶不同，因此不必保存完整前缀和，只需要记录奇偶。
处理当前元素后，若当前前缀为奇数，那么每一个历史偶前缀都可以作为左端之前的位置，产生一个以当前元素结尾的奇数和子数组，新增数量就是
evenCount。当前前缀为偶数时，同理新增oddCount。统计贡献后，将当前前缀登记到对应类别。每个历史位置都代表不同起点，所以保存出现次数而非是否存在；每个子数组只在其右端被处理时计入，避免重复。
初始空前缀的和为零，是一个偶前缀，因此
evenCount = 1、oddCount = 0。这使从数组首项开始的子数组也能统一写成两个前缀之差。当前奇偶通过
(sum + num) % 2更新，sum始终只保存零或一。每轮对累计答案取模，不影响以后按历史前缀频次继续计数。
解题步骤
- 登记空前缀为偶数一次，当前奇偶与答案为零。
- 扫描新元素并更新当前前缀奇偶。
- 将历史相反奇偶的前缀数量加入答案。
- 增加当前这一类前缀的数量，并对答案取模。
- 返回最终计数。
代码实现
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)$，只保存两类频次与固定数量的变量。
关键点总结
[!green]
- 前缀奇偶不同，区间差才是奇数。
- 历史频次同时表示所有可用左端，避免逐个枚举。
- 空前缀参与计数，统一覆盖从首项开始的区间。
- 完整前缀数值可丢弃，只保留奇偶仍足以判断。
易错点总结
[!yellow]
- 偶前缀初始设为零，会漏掉从数组开头开始的合法子数组。
- 累加同类前缀频次，会统计成偶数和区间。
- 只数奇数元素会漏掉长度大于一的合法区间，也不能判断多个奇数相加的结果。
- 本题要求模后答案，累计时不能忘记取模。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 560. 和为 K 的子数组 | 中等 | 同样按前缀分类，本题只关心奇偶，当前前缀与相反奇偶的历史前缀配对。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！