难度: Medium
给你一个整数数组 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
提示：
1 <= nums.length <= 500001 <= nums[i] <= 10^51 <= k <= nums.length运行时间: 574 ms
内存: 22.7 MB
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
odd = [-1]
for i in range(len(nums)):
if nums[i] % 2 == 1:
odd.append(i)
odd.append(len(nums))
final = 0
for i in range(1,len(odd)-k):
now = (odd[i]-odd[i-1]) * (odd[i+k]-odd[i+k-1])
final += now
return final
此题解首先统计数组中所有奇数的位置，并将这些位置的索引存储在一个列表`odd`中。为了方便处理边界情况，题解在`odd`列表的开头添加了一个-1（表示数组起始之前的位置），在末尾添加了`len(nums)`（表示数组结尾之后的位置）。接下来，题解通过遍历`odd`中的每个有效奇数位置的索引来计算每种可能的子数组的数量。对于每个有效的索引`i`（从1到`len(odd)-k`），计算从`odd[i-1]+1`到`odd[i+k-1]`的子数组，其中包含恰好`k`个奇数。通过计算两端奇数位置之间的间隔，可以确定每个这样的子数组可以在原数组中存在的不同位置数，最后将所有这些可能的位置数累加起来，得到最终结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
odd = [-1] # 初始化奇数索引数组，并添加-1作为辅助起点
for i in range(len(nums)):
if nums[i] % 2 == 1: # 判断当前数是否为奇数
odd.append(i) # 是奇数则记录索引
odd.append(len(nums)) # 在末尾添加nums长度作为辅助终点
final = 0 # 用于统计优美子数组的数量
for i in range(1, len(odd) - k):
now = (odd[i] - odd[i-1]) * (odd[i+k] - odd[i+k-1]) # 计算两侧可能的起始位置差的乘积
final += now # 将当前计算结果累加到final中
return final # 返回计算结果
在数组`odd`中添加-1和`len(nums)`作为起始和结束辅助点的主要原因是为了简化边界处理。添加-1意味着可以把数组前面没有元素的情况也统一处理，而添加`len(nums)`则表示数组之后没有更多元素的边界。这样的设置可以使得在计算子数组时，可以一致性地处理边界附近的情况，无需编写特殊的边界检查代码，从而提高代码的整洁性和可读性。
题解中使用两侧奇数位置差的乘积来计算可能的子数组位置的原理基于组合计数。给定一个包含恰好`k`个奇数的子数组，子数组的起始位置可以从前一个奇数后的任何一个位置开始（直到当前奇数的位置），结束位置则可以从最后一个奇数后的任何位置开始（直到下一个奇数之前）。因此，计算两侧奇数位置的差，实际上是计算起始位置和结束位置的选择范围。将这两个选择范围的长度相乘，就给出了所有可能的子数组的数量。
题解中选择先记录奇数的索引，而不是在遍历时直接计算子数组的数量，是因为这种方法更加灵活和高效。首先，一次遍历记录奇数索引为后续计算提供了必要的信息，并且避免了多次重复检查每个元素是否为奇数。其次，有了奇数索引的列表后，在后续处理中可以更容易地通过索引间的距离计算出满足条件的子数组数量，这种方式比直接在遍历中计算要直观且易于理解处理。
题解算法在处理前不需要对数组`nums`的长度或元素的值进行特殊处理或验证。算法本身已经通过添加-1和`len(nums)`处理了空数组或较短数组的情况。然而，需要注意的是，如果`k`大于实际奇数数量，那么在实际应用中我们应返回0，因为不可能有子数组包含比实际更多的奇数。此外，对于数组中元素的值，由于只关心元素是否为奇数，因此不需要对具体的数值做额外处理。