一【题目类别】

• 滑动窗口

二【题目难度】

• 中等

三【题目编号】

• 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<=nums.length<=50000$
• $1<=nums[i]<=10^5$
• $1<=k<=nums.length$

七【解题思路】

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

八【时间频度】

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

九【代码实现】

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;
    }
}

2. 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;
}

3. Python语言版

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        size = len(nums)
        res = 0
        index = [-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

4. 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;
    }
};

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版