LeetCode 1248. 统计「优美子数组」

地址 https://www.acwing.com/solution/leetcode/content/5801/

题目描述
给你一个整数数组 nums 和一个整数 k。

如果某个子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 ：

输入：nums = [,,,,], k =

输出：

解释：包含  个奇数的子数组是 [,,,] 和 [,,,] 。

示例 ：

输入：nums = [,,], k =

输出：

解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 ：

输入：nums = [,,,,,,,,,], k =

输出：

提示：

 <= nums.length <=

 <= nums[i] <= ^

 <= k <= nums.length

算法1
暴力枚举 就不说了 TLE了

比如
nums = [2,2,2,1,2,2,1,2,2,2], k = 2
暴力枚举肯定是
2 2 2 1 2 2 1
2 2 2 1 2 2 1 2
2 2 2 1 2 2 1 2 2
2 2 2 1 2 2 1 2 2 2

2 2 1 2 2 1
2 2 1 2 2 1 2
2 2 1 2 2 1 2 2
2 2 1 2 2 1 2 2 2

.....一共16组

观察规律
往滑动窗口方便考虑
我先计算出 开头结尾都是奇数 符合K个奇数的数组
然后在计算左右两边可以填写的的偶数数目
最后的答案-子数组的数目 ,其实是左边可以选择的方案数乘以右边可以选择方案数

也就是基本数组1,2,2,1 向左右扩展。
左边可填充的偶数乘以右边可填充的偶数
(左边可以填充3个2 ,右边可以填充3个2, 再加上最基本数组的奇数开头结尾也算是一种选择)
所以最终结果就是 (3+1)*(3+1) = 16

代码

class Solution {

public:

    int numberOfSubarrays(vector<int>& nums, int k) {

        if (nums.size() < k) return ; int ret = ;

        vector<int> v;

        for (int i = ; i < nums.size(); i++) {

            if (nums[i] %  != ) v.push_back(i);

        }

        //得到所有为奇数的下标索引

        vector<pair<int, int>> vp;

        int i = ;

        while (k + i <= v.size()) {

            int a = v[ + i];

            int b = v[k + i - ];

            vp.push_back({ a,b });

            i++;

        }

        //对于每个刚刚好是K个奇数 且奇数开头结尾的子数组 再进行计算

        for (int i = ; i < vp.size(); i++) {

            int a = vp[i].first;

            int b = vp[i].second;

            //计算左边有多少个偶数可以添加进来

            if (i == ) a = a+;

            else {

                a = a - vp[i - ].first;

            }

            //计算右边有多少个偶数可以添加进来

            if (i == vp.size() - ) b = nums.size() - b;

            else {

                b = vp[i + ].second - b;

            }

            ret += a * b;

        }

        return ret;

    }

};

LeetCode 1248. 统计「优美子数组」的相关教程结束。