统计「优美子数组」-- 滑动窗口

0x01.问题

给你一个整数数组 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

public int numberOfSubarrays(int[] nums, int k) 

0x02.详细思路分析

第一步，读题，发现题目的需求：

• 在数组中找出一些连续子数组，统计这些连续子数组的数目。
• 这些连续子数组需要满足的条件是，奇数个数等于k。

理清一下思路，发现着重点在于寻找子数组的数目，于是，一条很明显的思路就出来了，那就是，遍历所有可能的连续子数组，简单的写出下列的代码：

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int ans=0;
        for(int i=0;i<nums.length;i++){
            int cou=0;
            for(int j=i;j<nums.length;j++){
                if((nums[j]&1)==1){
                    cou++;
                }
                if(cou==k){
                    ans++;
                }
                if(cou>k){
                    break;
                }
            }
        }
        return ans;
    }
}

应该可以说已经解决了这个问题，但我们看一下时间复杂度：O（N^2），这很明显太高了，当数据量达到10^5的时候，已经无法短时间运算出来了。

我们需要对这个算法进行优化。

其实我们在写这个算法的时候应该已经感觉到这是一种不好的思路，为什么呢？因为我们在写这个代码的时候，就会发现，过于暴力，感觉到似乎做了很多不必要的重复运算。

其实我们的这种感觉，在指引着我们来对算法进行优化，我们的感觉是，重复运算的次数过多。在每一次更换子数组的起始点的时候，我们都要对后面的每个数进行判断，但其实，这里面的数很多已经在前面都判断过了，我们想，如果只判断一次就好了。

我们判断这些数的目的是什么？目的就是统计这个区间内奇数的数量，然后判断这个子数组是否满足条件。

我们要想突破O（N^2）的这个瓶颈，就一定不能去遍历子数组，因为遍历子数组的话，O（N^2）是绝对少不了的。那么我们就只剩下另一条思路，由奇数的个数，去计算出满足条件的子数组的数目。

假如，我们知道了在一段区间内，恰好有k个奇数，我们怎么去计算有多少满足条件的连续子数组数目呢？

• 首先，对于这段区间，最后一个数肯定是奇数，因为是通过最后一个数判断出来奇数个数等于k的，这段区间的第一个数暂时不清楚。
• 然后，对于求连续子数组的个数，最重要的是，确定子数组的起始点和终点，只要在起始点和终点之内包含了k个奇数，那么都是满足条件的。
• 假如，我们从第一个数开始向右边寻找这段区间内的第一个奇数，并记录下中间偶数的数目，这些偶数都是可以作为连续子数组的起始点的，因为不管怎样，这段区间的第一个奇数都还在它们后面。
• 再从最后一个数开始，向右去寻找下一个奇数，并记录中间偶数的数目，这些偶数都是可以当作连续子数组的尾部的，因为这段区间内最后一个奇数已经出现。
• 最后这段区间内的连续子数组的个数就是：起始点数目*终点数目，也就是这些的组合数。

通过上述思路，我们可以基本确定，如何遍历一次去得出满足条件的子数组的个数，接下来，确定整体的思路：

• 采用滑动窗口的思路，每次构造出一段满足区间内奇数个数恰为k的区间，然后计算这段区间。
• 计算完毕后，左指针右移，相应的奇数奇数器减一，不断重复上述过程。

0x03.解决代码–滑动窗口

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int ans=0;
        int oddCou=0;
        int left=0;
        int right=0;
        while(right<nums.length){
            if((nums[right++]&1)==1){
                oddCou++;
            }
            if(oddCou==k){
                int preRight=right;
                while(right<nums.length&&(nums[right]&1)==0){
                    right++;
                }
                int rightEvenCou=right-preRight;
                int leftEvenCou=0;
                while((nums[left]&1)==0){
                    leftEvenCou++;
                    left++;
                }
                ans+=(leftEvenCou+1)*(rightEvenCou+1);
                left++;
                oddCou--;
            }
        }
        return ans;
    }
}

ATFWUS --Writing By 2020–04-21