1248. 统计「优美子数组」

🎯 问题描述（来源于LeetCode）

描述：
给定一个整数数组 nums 和一个整数 k。如果一个连续子数组中恰好有 k 个奇数数字，我们就称这个子数组为「优美子数组」。
请返回这个数组中「优美子数组」的数目。

说明：

  • 子数组是连续的。
  • 1 <= nums.length <= 5 * 10^4。

示例：

  • 示例 1：
1
2
3
输入: nums = [1,1,2,1,1], k = 3
输出: 2
解释: 包含 3 个奇数的子数组有 [1,1,2,1] 和 [1,2,1,1]。
  • 示例 2：
1
2
输入: nums = [2,4,6], k = 1
输出: 0

💻 解题思路

思路：滑动窗口 + 容斥原理（基于您的代码）

算法步骤

  1. 将原数组 nums 转换为 0/1 数组：偶数 → 0，奇数 → 1。
  2. 定义辅助函数 atLeast(x)，返回原数组中奇数个数至少为 x 的连续子数组的个数。
    • 在 atLeast(x) 中：
      • 使用滑动窗口维护当前窗口内奇数的个数（即 pre）。
      • 遍历右端点 right，将 nums[right] 加入 pre。
      • 当 pre >= x 时，不断移动左指针 left（并减去移出的元素），直到 pre < x。
      • 此时，对于当前右端点，所有左端点 小于 left 的子数组（即起点 0 到 left-1）都满足奇数个数至少为 x，共有 left 个，累加到答案 ans。
  3. 利用容斥：恰好为 k 个奇数的子数组数 = atLeast(k) - atLeast(k+1)。
  4. 返回结果。

代码实现（您的代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from typing import List

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # 将原数组转为 0/1：奇数=1，偶数=0
        def isNum(num):
            return 1 if num % 2 == 1 else 0
        for i, num in enumerate(nums):
            nums[i] = isNum(num)
        
        # 统计奇数个数 >= x 的子数组个数
        def atLeast(x: int) -> int:
            ans = 0
            left = 0
            pre = 0
            for right, num in enumerate(nums):
                pre += num
                while left <= right and pre >= x:
                    pre -= nums[left]
                    left += 1
                ans += left
            return ans
        
        return atLeast(k) - atLeast(k + 1)

📊 性能分析

  • 时间复杂度：O(n)O(n)，三次遍历（一次转换 + 两次 atLeast），但每次遍历都是线性的，总体仍为 O(n)。
  • 空间复杂度：O(1)O(1)，仅使用常数个变量（原地修改数组，不算额外空间）。

思考

您的解法非常巧妙，将「恰好 k 个奇数」转化为「至少 k 个」与「至少 k+1 个」的差，完美复用了 LeetCode 930 题的滑动窗口模板。
关键点在于 ans += left：当窗口内奇数个数下降到小于 x 时，left 是第一个使得窗口不满足条件的左边界，因此所有比 left 小的左端点（即 0 到 left-1）与当前右端点构成的子数组都至少包含 x 个奇数。
这种写法简洁高效，无需处理双指针的复杂边界，是本题的经典解法之一。