---

1248. 统计「优美子数组」

• 标签：数组、哈希表、数学、前缀和、滑动窗口
• 难度：中等

题目链接

• 1248. 统计「优美子数组」 - 力扣

题目大意

描述：给你一个整数数组 $nums$ 和一个整数 $k$。如果某个连续子数组中恰好有 $k$ 个奇数数字，就认为这个子数组是「优美子数组」。

要求：返回这个数组中「优美子数组」的数目。

说明：

• $1 \le nums.length \le 50000$。
• $1 \le nums[i] \le 10^5$。
• $1 \le k \le nums.length$。

示例：

• 示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

• 示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

解题思路

思路 1：前缀和 + 哈希表

1. 核心思想

我们其实不关心数字的具体大小，只关心它是奇数还是偶数。可以把奇数看作 $1$，偶数看作 $0$，这样原数组就变成了一个只包含 $0$ 和 $1$ 的二进制数组。问题就转化为经典的「和为 $k$ 的子数组个数」问题。

前缀和是一种快速计算任意区间内元素之和的方法。定义 $prefix[i]$ 为数组前 $i$ 个元素的和（即前 $i$ 个数中奇数的个数）。那么区间 $[l, r]$ 的奇数个数就是 $prefix[r] - prefix[l-1]$。要找奇数个数恰好为 $k$ 的区间，就是找 $prefix[r] - prefix[l-1] = k$，即 $prefix[l-1] = prefix[r] - k$。

换句话说，遍历到位置 $r$ 时，我们想知道之前有多少个位置 $l-1$ 的前缀和等于 $prefix[r] - k$。用哈希表存储每个前缀和出现的次数，就可以 $O(1)$ 时间得到这个数量。

2. 具体步骤

第 1 步：初始化

• 哈希表 $count$，键为前缀和，值为该前缀和出现的次数。
• 初始时 $count[0] = 1$，表示前缀和为 $0$ 出现了 $1$ 次（空数组的情况）。
• $cur = 0$，记录当前遍历到的位置的前缀和（即已遇到的奇数个数）。
• $ans = 0$，记录结果。

第 2 步：遍历数组

对于每个元素 $num$：

• 如果 $num$ 是奇数，$cur += 1$。
• 在哈希表中查找 $cur - k$，如果存在，说明以当前位置为右端点的优美子数组有 $count[cur - k]$ 个，累加到 $ans$。
• 将当前的 $cur$ 在哈希表中的次数加 $1$。

第 3 步：返回结果

遍历结束后 $ans$ 就是答案。

结合示例 1 走一遍：

$nums = [1,1,2,1,1], k = 3$

$count = \{0: 1\}, cur = 0, ans = 0$

• $num = 1$（奇数）：$cur = 1$，查 $count[1-3]=count[-2]$ 不存在 → 记录 $count[1] = 1$
• $num = 1$（奇数）：$cur = 2$，查 $count[2-3]=count[-1]$ 不存在 → 记录 $count[2] = 1$
• $num = 2$（偶数）：$cur = 2$，查 $count[2-3]=count[-1]$ 不存在 → 记录 $count[2] = 2$
• $num = 1$（奇数）：$cur = 3$，查 $count[3-3]=count[0]=1$，$ans = 1$ → 记录 $count[3] = 1$
• $num = 1$（奇数）：$cur = 4$，查 $count[4-3]=count[1]=1$，$ans = 2$ → 记录 $count[4] = 1$

返回 $2$。

思路 1：代码

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # 哈希表记录每个前缀和出现的次数
        count = {0: 1}
        cur = 0   # 当前前缀和（即已遇到的奇数个数）
        ans = 0   # 结果

        for num in nums:
            # 遇到奇数，前缀和加 1
            if num % 2 == 1:
                cur += 1

            # 如果有前缀和为 cur - k 的记录，说明找到了优美子数组
            if cur - k in count:
                ans += count[cur - k]

            # 记录当前前缀和
            count[cur] = count.get(cur, 0) + 1

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $nums$ 的长度。每个元素只需要 $O(1)$ 时间处理（判断奇偶、更新前缀和、查询哈希表）。
• 空间复杂度：$O(n)$，哈希表在最坏情况下需要存储 $n + 1$ 个不同的前缀和值。

思路 2：滑动窗口

1. 核心思想

维护一个窗口，使得窗口内恰好包含 $k$ 个奇数。对于每个这样的窗口，统计它向左和向右能扩展多少个偶数，这些扩展出来的位置和窗口本身组合起来都形成优美子数组。

2. 具体步骤

第 1 步：记录所有奇数的下标

创建一个数组 $odd\_idx$ 记录每个奇数的位置，方便快速定位。

第 2 步：遍历奇数下标数组

对于第 $i$ 个奇数（从 $0$ 开始）：

• 第 $i$ 个奇数和第 $i + k - 1$ 个奇数之间（包含两端）就是包含 $k$ 个奇数的最小区间。
• 这个区间向左可以扩展到前一个奇数之后（或数组开头），向右可以扩展到后一个奇数之前（或数组结尾）。
• 可扩展的左边位置数 = $odd\_idx[i] - odd\_idx[i-1]$（或 $odd\_idx[0] + 1$ 如果是第一个区间）。
• 可扩展的右边位置数 = $odd\_idx[i+k] - odd\_idx[i+k-1]$（或 $n - odd\_idx[last]$ 如果是最后一个区间）。
• 左右扩展数相乘，就是以当前 $k$ 个奇数为核心的所有优美子数组数量。

第 3 步：累加并返回结果

将所有区间贡献的数量相加。

思路 2：代码

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 记录所有奇数的位置（方便起见加一个虚拟头 -1）
        odd_idx = [-1]
        for i in range(n):
            if nums[i] % 2 == 1:
                odd_idx.append(i)
        odd_idx.append(n)  # 虚拟尾

        ans = 0
        # 遍历奇数下标数组，每 k 个一组
        for i in range(1, len(odd_idx) - k):
            # 以第 i 个奇数到第 i+k-1 个奇数作为核心区间
            # 左边可扩展的偶数个数
            left = odd_idx[i] - odd_idx[i - 1]
            # 右边可扩展的偶数个数
            right = odd_idx[i + k] - odd_idx[i + k - 1]
            ans += left * right

        return ans

思路 2：复杂度分析

• 时间复杂度：$O(n)$，需要一次遍历定位所有奇数位置。
• 空间复杂度：$O(n)$，用于存储奇数位置下标数组。