LeetCode 1248. 统计「优美子数组」
题目描述
题意分析
统计恰好包含
k个奇数的连续子数组数量。元素的具体数值不影响答案，只需把奇数看成1、偶数看成0，问题就变成统计区间和等于k的子数组。
解法：前缀奇数个数计数
核心思路
[!blue]
设
P[i]为前i个元素中的奇数个数，P[0] = 0。区间[l, r)恰有k个奇数，等价于P[r] - P[l] = k，也就是P[l] = P[r] - k。从左到右维护当前前缀奇数数
oddCount，用prefixCount[c]记录此前有多少个前缀包含c个奇数。处理完当前元素后，每个奇数数为oddCount - k的历史前缀都对应一个合法左端，因此它的频次就是当前右端新增的答案数。不同前缀位置即使奇数数相同，也对应不同的子数组，所以要保存次数，不能只保存是否出现过或某一个下标。偶数虽然不增加
oddCount，仍会产生新的前缀位置，必须照常查询并登记。初始
prefixCount[0] = 1代表空前缀，用于统计从数组开头开始的区间。每轮先使用历史计数，再登记当前前缀；所有区间都按自己的右端点统计一次，不会重复。
解题步骤
- 前缀奇数数只会在
0到n之间，创建长度为n + 1的频次数组，并登记一次空前缀。- 遍历元素，遇到奇数才让
oddCount加一。- 若
oddCount >= k，把prefixCount[oddCount - k]加入答案；否则历史前缀不可能有负的奇数数，当前没有贡献。- 不论当前元素是奇数还是偶数，都执行
prefixCount[oddCount]++，最后返回累计答案。
代码实现
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int[] prefixCount = new int[nums.length + 1];
// 空前缀提供从数组下标零开始的子数组。
prefixCount[0] = 1;
int oddCount = 0;
int ans = 0;
for (int num : nums) {
if (num % 2 == 1) {
oddCount++;
}
// 历史前缀比当前少 k 个奇数，就能构成一个合法区间。
if (oddCount >= k) {
ans += prefixCount[oddCount - k];
}
// 偶数也产生新的前缀位置，同样需要登记。
prefixCount[oddCount]++;
}
return ans;
}
}
func numberOfSubarrays(nums []int, k int) int {
prefixCount := make([]int, len(nums)+1)
// 空前缀提供从数组下标零开始的子数组。
prefixCount[0] = 1
oddCount := 0
ans := 0
for _, num := range nums {
if num%2 == 1 {
oddCount++
}
// 历史前缀比当前少 k 个奇数，就能构成一个合法区间。
if oddCount >= k {
ans += prefixCount[oddCount-k]
}
// 偶数也产生新的前缀位置，同样需要登记。
prefixCount[oddCount]++
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(n)$，前缀奇数数范围为零到 n。
关键点总结
[!green]
- 频次代表不同前缀位置，不能只记录一个下标。
- 每次右端都可能贡献答案，包括当前元素为偶数时。
易错点总结
[!yellow]
- 缺少空前缀，会漏掉从数组开头起算的答案。
- 只在遇奇数时登记前缀，会漏掉偶数形成的不同左端。
- c 小于 k 时仍按 c−k 访问数组，会出现负下标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 930. 和相同的二元子数组 | 中等 | 把奇数映射为1、偶数映射为0，恰有k个奇数就变成二元子数组和为k。 |
| 992. K 个不同整数的子数组 | 困难 | 同样可用atMost(k)-atMost(k-1)统计恰好条件，本题预算是奇数数量，原题是不同值种类数。 |
| 560. 和为 K 的子数组 | 中等 | 前缀和配合哈希表查找所需历史前缀；本题把奇数映射为 1 后统计精确数量，该题存前缀出现次数以统计精确和。 |
| 325. 和等于 k 的最长子数组长度 | 中等 | 前缀和配合哈希表查找所需历史前缀；本题把奇数映射为 1 后统计精确数量，该题存最早前缀下标以最大化长度。 |
| 437. 路径总和 III | 中等 | 前缀和配合哈希表查找所需历史前缀；本题把奇数映射为 1 后统计精确数量，该题沿树路径维护前缀次数并回溯恢复。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！