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
提示：
- 1 <= nums.length <= 50000
- 1 <= nums[i] <= 10^5
- 1 <= k <= nums.length
解题思路
思路：双指针（滑动窗口）
首先，理解题目的内容。
【如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。】
这个就是【优美子数组】的定义，需要注意，子数组需连续，且有 k 个奇数数字。
那么在这里转换下思路：也就是先找到连续 k 个奇数的子数组，那么前后添加任意个偶数（注意只能是偶数，可以是 0 个），这里都能构建【优美子数组】。
那么具体的算法：
- 定义双指针，先移动右指针，扩大滑动窗口，使数组含有 k 个奇数；
- 当滑动窗口包含 k 个奇数时，这个时候考虑构建【优美子数组】：
- 计算滑动窗口第一个奇数左边的偶数个数
left_even_count。如前面所述，这里偶数可以是 0 个。所以计算出来的数目需加 1。 - 计算滑动窗口第 k 个奇数右边的偶数个数
right_even_count。与上面的一样，计算数目需加 1。
- 计算滑动窗口第一个奇数左边的偶数个数
- 因为题目要求，【优美子数组】为含有连续包含 k 个奇数的子数组。那么在最简子数组的基础上左右添加偶数元素同样成立。那么这里的组合数为
(left_even_count + 1) * (right_even_count + 1)。
具体实现代码如下。
代码实现
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
# 定义双指针
left, right = 0, 0
# 统计奇数个数
odd_count = 0
# 返回结果
ans = 0
# 数组长度
length = len(nums)
while right < length:
# 先移动右指针，统计奇数个数
if nums[right] % 2 == 1:
odd_count += 1
right += 1
# 当滑动窗口有 k 个奇数时，统计优美子数组个数
if odd_count == k:
# 这个时候向右边扩大窗口，统计偶数个数，
# 遇到奇数或者越界则停止
sign = right
while right < length and nums[right] % 2 == 0:
right += 1
# 计算窗口右边偶数个数
right_even_count = right - sign
# 统计窗口右边的偶数个数后，
# 现在统计窗口左边的偶数个数
left_event_count = 0
while nums[left] % 2 == 0:
left_event_count += 1
left += 1
# 现在计算组合数，添加到结果中
# 注意：偶数个数可以为 0 个，
# 所以前面计算的左右偶数个数需加 1
ans += (left_event_count + 1) * (right_even_count + 1)
# 这个时候，数组后续可能还有其他的组合
# left 在此时指向的是第一个奇数，所以向后移动一步
left += 1
odd_count -= 1
return ans
实现结果
以上就是使用双指针（滑动窗口）的思路，运用固定含 k 个奇数的窗口，左右寻找偶数，进行组合的方法，用以解决《1248. 统计「优美子数组」》问题的主要内容。