LeetCode 1248. 统计「优美子数组」

提示：

• 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