Leetcode 1248.统计「优美子数组」【C++】

地址：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

解题思路

首先，这个题是需要找规律的，要怎么怎么去计算优美子数组的个数，不然就算是暴力解那也没法下手。

这个题 读懂题就很重要，通过题目给出的三个示例，以示例3为例，题目要求是“恰有” k 个奇数数字的“连续”子数组，所以在示例3种，要找的是恰有 2 个连续奇数数字的连续子数组，而示例3种仅有 2 个奇数数字，显然必须要有 1,2,2,1 这部分。剩下可能的组合仅与左右两侧的偶数个数有关，简要列举可能的几个情况如下：

//左侧共有连续的3个偶数，可能的情况有4种

//左侧没有更多的偶数（为数组边界或相邻位置是奇数）
1,2,2,1
//左侧有1个偶数
2,1,2,2,1
//左侧有2个偶数
2,2,1,2,2,1
左侧有3个偶数
2,2,2,1,2,2,1

//右侧同理

可以看出，左侧或者右侧有 m 个偶数，就有 m + 1 种可能的情况。如果左侧有 a 种可能的情况，右侧有 b 种可能的情况，则共有 a * b 种情况。

由此，我们只需要遍历所有可能的连续 k 个奇数的情况，分别计数左右两侧偶数的个数并计算可能的组合情况，加到总的优美子数组的个数 ans 中即可。于是我想到了用双指针的办法解题，这就是一个快慢指针的题目，只不过对指针的修改情况稍微复杂一些。只考虑奇数，快指针找到第 k 个奇数，慢指针才开始找第一个奇数，也就是慢指针到快指针之间始终保持 k 个奇数，在遍历的过程中同时就计数偶数数字的个数，避免了重复遍历。剩下的工作就是计算优美子数组个数以及正确的修改指针。

另外，其实可以知道如果数组中的奇数个数小于 k ，是不可能有满足条件的情况的，也就说可以直接返回 0 。但在我的代码中，仅当找到 k 个奇数，才可能进行进一步的计算，所以如果找不到 k 个奇数，则返回初始值 0 。

代码

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int ans = 0;//返回值
        //模拟快慢指针，快指针比慢指针快k个奇数
        int front = 0;
        int slow = 0;
        for (; front < nums.size(); front++) {
            //前k个奇数不做处理
            if (nums[front] % 2 == 1 && k != 0) {
                k--;
            }
            //从第k个奇数开始计算优美子数组的个数
            if (nums[front] % 2 == 1 && k == 0) {
                int left = 1;//左右两侧偶数可能的组合情况
                int right = 1;//默认为1，即一个偶数也没有
                //慢指针遍历到下一个奇数，同时计数偶数的个数，m个偶数有m+1种可能的情况
                for (; slow < nums.size(); slow++) {
                    if (nums[slow] % 2 == 1) {
                        slow++;
                        break;
                    }
                    left++;
                }
                //快指针遍历到下一个计数，同时计数偶数个数
                for (int t = front + 1; t < nums.size(); t++) {
                    if (nums[t] % 2 == 1) {
                        break;
                    }
                    right++;
                }
                //当前k个连续计数组成的子数组可能的组合情况
                ans += left * right;
            }
        }
        return ans;
    }
};