恰好 K 个奇数的子数组数量，为什么可以转成前缀奇数个数？

简化版

恰好 K 个奇数的子数组，可以把奇数记为 1、偶数记为 0。

问题就变成二进制数组中和为 K 的子数组个数。

遍历时维护奇数前缀个数 oddCount，答案增加之前出现过的 oddCount - k 次数。

详细版

奇偶性比具体数值更重要。

遇到奇数时，当前前缀奇数数加 1；遇到偶数则不变。如果当前位置的前缀奇数数为 oddCount，那么要让某段子数组恰好有 k 个奇数，左侧前缀应该是 oddCount - k。

哈希表记录每个前缀奇数数出现的次数。

初始化 count[0] = 1，表示空前缀。时间复杂度 O(n)，空间复杂度 O(n)；也可以用“至多 K 个奇数 - 至多 K-1 个奇数”的滑动窗口做法。

完整版教学

一、为什么只看奇偶性

题目问的是“奇数个数”，不是子数组元素和。一个奇数贡献 1 个目标单位，一个偶数贡献 0 个目标单位。因此可以把原数组映射成 0/1 数组：奇数为 1，偶数为 0。这样恰好 K 个奇数，就等价于映射数组的区间和为 K。

记忆钩子：统计某类元素出现 K 次，可以把属于该类记为 1，不属于记为 0。

二、前缀奇数个数的公式

设 prefixOdd[j] 是到位置 j 的奇数累计数。如果区间 (i, j] 中有 k 个奇数，则：

prefixOdd[j] - prefixOdd[i] = k
prefixOdd[i] = prefixOdd[j] - k

所以遍历到当前位置时，只需要知道之前有多少个前缀奇数数等于 oddCount - k。

三、带数字推演

数组 [1,1,2,1,1]，k = 3。映射后是 [1,1,0,1,1]。

初始 count[0]=1
i=0 odd=1，找 -2，无
i=1 odd=2，找 -1，无
i=2 odd=2，找 -1，无
i=3 odd=3，找 0，有 1 个，ans=1
i=4 odd=4，找 1，有 1 个，ans=2

答案是 2，对应 [1,1,2,1] 和 [1,2,1,1]。

四、代码模板

实现如下：

function numberOfSubarrays(nums, k) {
  const count = new Map([[0, 1]])
  let oddCount = 0
  let ans = 0
  for (const x of nums) {
    if (x % 2 !== 0) oddCount++
    ans += count.get(oddCount - k) || 0
    count.set(oddCount, (count.get(oddCount) || 0) + 1)
  }
  return ans
}

哈希表存次数，因为同一个前缀奇数数可能在多个偶数位置重复出现，这些重复都会形成不同子数组。

五、和滑动窗口解法的关系

因为映射后是非负数组，也可以统计“最多 K 个奇数”的子数组数量，再相减得到恰好 K 个：

exactly(k) = atMost(k) - atMost(k - 1)

方法	依赖条件	优点
前缀和哈希	通用计数公式	直接表达恰好 K
滑动窗口相减	非负贡献	空间可做到 O(1)

两种方法都值得掌握。

六、常见误区与追问

误区：用元素值求和。 本题只关心奇数数量，偶数具体大小没有意义。
误区：哈希表存第一次位置。 求个数要存出现次数，不是存位置。
误区：忘记空前缀。 从下标 0 开始的漂亮子数组会漏掉。
追问：偶数有什么作用？ 偶数不增加奇数数，但会让相同前缀状态重复，从而增加组合数量。
追问：能否用滑动窗口？ 可以，用至多 K 减至多 K-1，因为奇数贡献是非负的。

这些点说明你是否会把计数条件转成前缀状态。

七、加强记忆

恰好 K 个奇数记成“奇数变 1，偶数变 0，找和为 K”。遍历时维护 oddCount，查 oddCount-k 出现过几次。因为要统计数量，哈希表存次数；因为可能从开头开始，初始化 0 出现 1 次。偶数虽然贡献 0，但它会制造更多相同前缀，别忽略它。

简化版

详细版