试水刷题，先从简单的练起。

题目

1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 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
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

解题思路

这题其实可以当作一道排列组合题来做，老样子我们先构造测试用例，画图。

用例就选题目中的示例3吧：nums = [2,2,2,1,2,2,1,2,2,2], k = 2

首先我们找出所有的奇数备用，在这个样例中，恰好只有2个奇数。

然后，我们寻找一下第一个最短的 『优美子数组』，可以看到是中间的 1221 。

简单推理就可知，这样的最短子数组，一定是两端都是奇数的。

在这个样例中，由于只有两个奇数，恰好只有 1 个两端都是奇数的情况，方便分析。

接下来，我们需要看一下这个最短的情况，可以怎样变成其它的情况。

从 1221 变成 21221 12212 221221 等情况，本质上就是在 1221 的基础上，增加不同的前缀和后缀。

在这个样例中，前缀有 4 种取法 "222" "22" "2" "" ，后缀也有相同的 4 种取法。

可见，能从 1221 扩展出的优美子数组，总共有 16 种 ，这也是最终的答案。

接下来，我们来理解一个更长的情况，看看更多奇数的情况如何处理。

先来构造测试数据：nums = [2,2,2,1,2,2,1,2,2,2,1,1,2,2,2,1], k = 2

有没有注意到上面的图里，我故意在两边加了 # ，现在我们使用 # 将这个数组分割一下，如图。

从图中可以看到，其实当我们有超过 k 个奇数存在的时候，其实还是可以用一样的方式来进行计算的。

假如有 n 个奇数，那么当我们找的两端为奇数的优美数组，首位是第 i 个奇数的时候，末位必然是第 i+k-1 个奇数。

而第 i+k-1 个奇数，尾部可接的可能性数量，就是第 i+k 个奇数的前缀数量。

所以，第 i 个奇数的前缀数量，乘以第 i+k 个奇数的前缀数量，就是这种情况下的可能性数量。

遍历整个数组，维护相应的数据并累加，就可以快速的得到答案了。

代码

时间复杂度方面，其实只需要一次循环就可以完成遍历和计算的操作，也就是 O(n)。

空间复杂度方面，为了省事直接开了等长的数组，所以也是 O(n) ，要优化的话，其实可以只存 k 个前缀数。

不过已经跑双百了就懒得优化啦~

func numberOfSubarrays(nums []int, k int) int {
    odd := make([]int, len(nums)+1)
    oddNum, prefixLen := 0, 0
    ans := 0
    for i := 0; i <= len(nums); i++ {
        prefixLen += 1 //自己也要算进去
        if i == len(nums) || nums[i]%2 == 1 {
            odd[oddNum] = prefixLen
            if oddNum >= k {
                ans += odd[oddNum-k] * odd[oddNum]
            }
            oddNum += 1
            prefixLen = 0
        }
    }
    return ans
}