给你一个整数数组 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
网友评论