Leetcode 1248.统计「优美子数组」【C++】
本文最后更新于:2022年3月23日 晚上
地址: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;
}
};