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

本文最后更新于:2020年7月4日 晚上

地址: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;
    }
};