统计「优美子数组」 图解题解
这道题到底在问什么
- 输入
- nums = [1,1,2,1,1], k = 2
- 输出
- 5
最优解：一步一步想明白
- 3思路一句话：边扫边记前缀奇数个数 odd，查「odd−k」在哈希表出现过几次就新增几段；哈希表初始放 {0:1}。下面一步步演给你看。
- 4出发前：当前前缀奇数个数 odd = 0。哈希表先记一笔 {0: 1}，代表「一个数都还没扫」这个起点。
- 5指针 i 走到下标 0，这一格的值是 1。是奇数，前缀奇数个数 odd 要加一。
- 6算上这一格，从开头到下标 0 这整段前缀里，奇数一共 1 个（高亮的就是当前前缀）。
- 7要凑「恰好 2 个奇数」，就找更早出现过 odd = -1 的位置：哈希表里 -1 出现过 0 次（命中行高亮），于是新增 0 段优美子数组，累计 0 段。
- 8最后把当前前缀奇数个数 odd = 1 记进哈希表（新增/累加的那行高亮），留给后面的位置来查。
- 9指针 i 走到下标 1，这一格的值是 1。是奇数，前缀奇数个数 odd 要加一。
- 10算上这一格，从开头到下标 1 这整段前缀里，奇数一共 2 个（高亮的就是当前前缀）。
- 11要凑「恰好 2 个奇数」，就找更早出现过 odd = 0 的位置：哈希表里 0 出现过 1 次（命中行高亮），于是新增 1 段优美子数组，累计 1 段。
- 12最后把当前前缀奇数个数 odd = 2 记进哈希表（新增/累加的那行高亮），留给后面的位置来查。
- 13指针 i 走到下标 2，这一格的值是 2。是偶数，前缀奇数个数 odd 保持不变。
- 14算上这一格，从开头到下标 2 这整段前缀里，奇数一共 2 个（高亮的就是当前前缀）。
- 15要凑「恰好 2 个奇数」，就找更早出现过 odd = 0 的位置：哈希表里 0 出现过 1 次（命中行高亮），于是新增 1 段优美子数组，累计 2 段。
- 16最后把当前前缀奇数个数 odd = 2 记进哈希表（新增/累加的那行高亮），留给后面的位置来查。
- 17指针 i 走到下标 3，这一格的值是 1。是奇数，前缀奇数个数 odd 要加一。
- 18算上这一格，从开头到下标 3 这整段前缀里，奇数一共 3 个（高亮的就是当前前缀）。
- 19要凑「恰好 2 个奇数」，就找更早出现过 odd = 1 的位置：哈希表里 1 出现过 1 次（命中行高亮），于是新增 1 段优美子数组，累计 3 段。
- 20最后把当前前缀奇数个数 odd = 3 记进哈希表（新增/累加的那行高亮），留给后面的位置来查。
- 21指针 i 走到下标 4，这一格的值是 1。是奇数，前缀奇数个数 odd 要加一。
- 22算上这一格，从开头到下标 4 这整段前缀里，奇数一共 4 个（高亮的就是当前前缀）。
- 23要凑「恰好 2 个奇数」，就找更早出现过 odd = 2 的位置：哈希表里 2 出现过 2 次（命中行高亮），于是新增 2 段优美子数组，累计 5 段。
- 24最后把当前前缀奇数个数 odd = 4 记进哈希表（新增/累加的那行高亮），留给后面的位置来查。
- 25整趟扫完，恰好含 2 个奇数的优美子数组一共 5 段，这就是答案。
⚠️ 容易写错的地方
✗ 错：忘了一开始放 {0: 1}
✓ 对：哈希表初始就放 count[0] = 1
从开头起就含 k 个奇数的子数组，要靠「空前缀 odd=0」来配对，漏放就会少算这些段
✗ 错：先记 count[odd] 再查 count[odd−k]
✓ 对：必须先查再记
顺序反了会把当前这个前缀自己也算进配对，凑出长度为 0 的假子数组
✗ 错：把偶数也给 odd 加一
✓ 对：只有奇数才 odd += 1
odd 的定义是「前缀里奇数的个数」，偶数不能影响它，否则配对全乱
完整代码（Python / C++ / Java）
Python
def numberOfSubarrays(nums, k):
count = {0: 1} # 前缀奇数个数 -> 出现次数
odd = res = 0
for x in nums:
odd += x & 1 # 奇数才 +1
res += count.get(odd - k, 0) # 凑出 k 个奇数
count[odd] = count.get(odd, 0) + 1
return resC++
int numberOfSubarrays(vector<int>& nums, int k){
unordered_map<int,int> cnt{{0,1}};
int odd = 0, res = 0;
for (int x : nums) {
odd += x & 1;
res += cnt.count(odd - k) ? cnt[odd - k] : 0;
cnt[odd]++;
}
return res;
}Java
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
Map<Integer,Integer> cnt = new HashMap<>();
cnt.put(0, 1);
int odd = 0, res = 0;
for (int x : nums) {
odd += x & 1;
res += cnt.getOrDefault(odd - k, 0);
cnt.merge(odd, 1, Integer::sum);
}
return res;
}
}复杂度
时间
O(n)
指针把数组从头到尾扫一遍，每格只查一次哈希表、记一次
空间
O(n)
哈希表最多记 n+1 种不同的前缀奇数个数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计「优美子数组」 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
odd 和哈希表里的值分别代表什么？+
odd 是「从开头扫到当前位置，一共遇到几个奇数」；哈希表的键是某个 odd 值，值是这个 odd 值在之前的位置上出现过几次。用 count[odd−k] 就能数出有多少个左端点能凑成恰好 k 个奇数。
为什么用 odd−k 去查，而不是 odd+k？+
子数组的奇数个数 = 右端 odd − 左端前一格 odd。要它等于 k，左端前一格的 odd 就得是 odd−k。所以查的是更小的那个值 odd−k。
和「滑动窗口」解法比有什么区别？+
滑动窗口要做两次 atMost(k)−atMost(k−1)，逻辑绕；前缀计数法一趟扫完、思路统一（和「和为 K 的子数组」是同一套模板），更好写也更好记。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 统计「优美子数组」 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。