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

1248. 统计「优美子数组」

---

题目来源：https://leetcode-cn.com/problems/count-number-of-nice-subarrays

题目

---

给你一个整数数组 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. 统计「优美子数组」》问题的主要内容。

---

欢迎关注微信公众号《书所集录》