leetcode-优美子数组.md

2020-04-22

链接：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

解题思路：

一. 滑动窗口

定义两个指针和奇数个数，left, right, num, 控制right指针先遍历数组，遇到奇数则num++
当奇数个数等于k时，即left~right窗口里包含k个奇数，且right在最右边界，开始做以下处理：
- right继续右移，直到遇到新的奇数，统计中间的偶数数量 rightEvenCount
- left开始右移，直到遇到奇数，此时left为窗口左边界，统计移动过程中的偶数数量， leftEvenCount
- 最终这个窗口的优美子数组数目为： (leftEvenCount + 1) * (rightEvenCount + 1)，结果加到最终返回的结果result中
- right 继续遍历，重复上述操作

具体代码如下：

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int left=0, right=0, num=0;
        int res=0;
        while (right < nums.length) {
            if ((nums[right++] & 1)==1) {
                num++;
            }
            // 该滑动窗口中奇数为k个
            if (num == k) {
                int leftEven=0,rightEven=0;
                int temp = right;
                while (right < nums.length && (nums[right]&1)==0) {
                    right++;
                }
                rightEven = right-temp;
                while((nums[left]&1)==0) {
                    left++;
                    leftEven++;
                }
                res += (rightEven+1)*(leftEven+1);
                left++;
                num--;
            }
        }
        return res;
    }
}

二. 前缀项和

定义 pre[i] 为[0:i]中奇数的个数
每次遍历，计算当前数组的奇数个数sum，当sum>=k 时，在最终结果res中加上前缀项和为 sum - k 的个数

具体代码：

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int[] pre = new int[nums.length+1];
        int res=0, sum=0;
        pre[0] = 1;
        for (int num:nums) {
            sum += num & 1;
            // 截止此时，数组中有sum个奇数的数量
            pre[sum]++;
            if (sum >= k) {
                res += pre[sum - k];
            }
        }
        return res;
    }
}