一【题目类别】

滑动窗口

二【题目难度】

中等

三【题目编号】

1248.统计「优美子数组」

四【题目描述】

给你一个整数数组 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 <= n u m s . l e n g t h <= 50000$
$1 <= nums[i] <= 10^5$
$1 <= k <= n u m s . l e n g t h$

七【解题思路】

利用滑动窗口的思想
记录数组中奇数的索引下标，将所有奇数的索引下标存储到新的数组中，长度需要在之前的基础上加2，用来保持左窗口边界和右窗口边界，新加的两个位置分别位于新数组的最左边和最右边
每个窗口中的奇数的数量刚好满足题意，此时还可以继续向左右拓展，就需要移动左右窗口，左右拓展到奇数停止，如果不停止就不满足题目要求的奇数个数
位于最左边和最右边的值为了计算到不拓展的情况，否则会忽略这种情况
然后把左边拓展的情况数乘以右边拓展的情况数，就是最终此位置满足要求的窗口个数，也就是满足要求的子数组个数
然后汇总每次的结果
最后返回结果即可

八【时间频度】

时间复杂度： $O (n)$ ， $n$ 为传入数组的大小
空间复杂度： $O (1)$

九【代码实现】

Java语言版

class Solution {public int numberOfSubarrays(int[] nums, int k) {int res = 0;int len = nums.length;int[] index = new int[len + 2];int odd_count = 0;for(int i = 0;i<len;i++){if((nums[i] & 1) == 1){index[++odd_count] = i;}}index[0] = -1;index[odd_count + 1] = len;for(int i = 1;i + k < odd_count + 2;i++){res += (index[i] - index[i - 1]) * (index[i + k] - index[i + k - 1]);}return res;}
}

C语言版

int numberOfSubarrays(int* nums, int numsSize, int k)
{int len = numsSize;int* index = (int*)malloc(sizeof(int) * (len + 2));int odd_count = 0;int res = 0;for(int i = 0;i<len;i++){if((nums[i] & 1) == 1){index[++odd_count] = i;}}index[0] = -1;index[odd_count + 1] = len;for(int i = 1;i + k<odd_count + 2;i++){res += (index[i] - index[i - 1]) * (index[i + k] - index[i + k - 1]);}return res;
}

Python语言版

class Solution:def numberOfSubarrays(self, nums: List[int], k: int) -> int:size = len(nums)res = 0index = [-1]for i in range(0,size):if nums[i] & 1 == 1:index.append(i)index.append(size)for i in range(1,len(index) - k):res += (index[i] - index[i - 1]) * (index[i + k] - index[i + k - 1])return res

C++语言版

class Solution {
public:int numberOfSubarrays(vector<int>& nums, int k) {int len = nums.size();int* index = (int*)malloc(sizeof(int) * (len + 2));int odd_count = 0;int res = 0;for(int i = 0;i<len;i++){if((nums[i] & 1) == 1){index[++odd_count] = i;}}index[0] = -1;index[odd_count + 1] = len;for(int i = 1;i + k<odd_count + 2;i++){res += (index[i] - index[i - 1]) * (index[i + k] - index[i + k - 1]);}return res;}
};