Leetcode每日一题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

解题思路
找到满足要求长度为K的数组，然后左右移动直到碰到下个奇数为止，统计出满足要求的数组个数。

举例分析：
案列1：一个数组arr ： { 8 6 7 2 2 3 4 6 } ，其中K=2
枚举出符合要求的子数组：
第一组：
{ 7 2 2 3 }
{ 7 2 2 3 4 }
{ 7 2 2 3 4 6 }
第二组：
{ 6 7 2 2 3 }
{ 6 7 2 2 3 4 }
{ 6 7 2 2 3 4 6 }
第三组：
{ 8 6 7 2 2 3 }
{ 8 6 7 2 2 3 4 }
{ 8 6 7 2 2 3 4 6 }

观察规律发现，数组的个数由K数组左侧的偶数个数m和右侧的偶数个数n决定，即(m+1)*(n+1)
需要注意的是为什么+1 ，是因为 { 7 2 2 3 }本身也可以作为起点和终点

接下来我们看案列2，稍微复杂一点，数组中的奇数个数大于K(k=2)：
{ 2 3 2 7 2 9 2 }
此时讨论满足需求的数组时就需要考虑在这3个奇数中进行组合的问题了，并且左右扩张时需要注意下个奇数的位置：
第一组：3 和7为界，共4种
{ 3 2 7}
{ 2 3 2 7}
{ 2 3 2 7 2 }
{ 3 2 7 2}
第二组：7 和 9为界，共4种
{ 7 2 9 }
{ 7 2 9 2 }
{ 2 7 2 9 }
{ 2 7 2 9 2 }
所以满足要求的组和一共是 4 + 4 = 8

通过上面的描述，抽象出数据模式，每种子情况：
(arr[i] - arr[i-1]) * (arr[i+k] - arr[i+k-1])，其中arr是过滤之后的奇数数组。

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {

        int len = nums.length;
        int[] odd = new int[len+2];
        int index = 0;
        
        //过滤奇数，放入新数组
        for(int i=0;i<len;i++)
        {
            if((nums[i] & 1) == 1) odd[++index] = i;
        }

        //扩充两个边界，方便后续i-1 和 i+1 越界问题
        odd[0] = -1;
        odd[index+1] = len;
        
        int res = 0;
        for(int i=1;i+k < index+2;i++)
        {
            res += (odd[i] - odd[i-1]) * (odd[i+k] - odd[i+k-1]);
        }

        return res;

    }
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。