题目大意：
统计「优美子数组」
给你一个整数数组 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 <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1248
解题思路分析：
本题这种寻找连续区间的题目，很容易想到使用Sliding Window来解题。即找到所有的区间[i, j]，保证在区间内存在k个奇数即可。对于如何找到所有区间，我们来举例说明，比如存在以下数组，并且k为1：
int nums = [2, 4, 3, 6, 8]; int k = 1;
很显然，数组中只有1个奇数3，其他均为偶数，先看3的左边，存在2个偶数，这两个偶数与3能组成3个子数组：
int nums = [2, 4, 3, 6, 8]; // 原数组 int sub1 = [3]; // 1个奇数自己组成的子数组 int sub2 = [4, 3]; // 加入4 int sub3 = [2, 4, 3]; // 加入2
再看奇数3的右边，也存在2个偶数，因为左边存在3个子数组，因此每次向左边的子数组中加入一个数字，子数组的个数都会加3，比如，先加入6：
int nums = [2, 4, 3, 6, 8]; // 原数组 int sub4 = [3, 6]; // 加入6 int sub5 = [4, 3, 6]; // 加入6 int sub6 = [2, 4, 3, 6]; // 加入6
接下来再加入8：
int nums = [2, 4, 3, 6, 8]; // 原数组 int sub7 = [3, 6, 8]; // 加入8 int sub8 = [4, 3, 6, 8]; // 加入8 int sub9 = [2, 4, 3, 6, 8]; // 加入8
一共产生了9个子数组：
int sub1 = [3]; // 1个奇数自己组成的子数组 int sub2 = [4, 3]; // 加入4 int sub3 = [2, 4, 3]; // 加入2 int sub4 = [3, 6]; // 加入6 int sub5 = [4, 3, 6]; // 加入6 int sub6 = [2, 4, 3, 6]; // 加入6 int sub7 = [3, 6, 8]; // 加入8 int sub8 = [4, 3, 6, 8]; // 加入8 int sub9 = [2, 4, 3, 6, 8]; // 加入8
由此我们可以得到一个规律，在奇数左边加上一个偶数，可以得到一个新的子数组，在奇数右边加上一个偶数，可以得到n个新的子数组（n为左边子数组的个数）。
这里也可以换一种思考方式，奇数与左边的2个偶数可以组成3个子数组，同理，奇数与右边的2个偶数也可以组成3个子数组，因此，总的组合数为左右两边的个数相乘，即3乘以3等于9。
所以解题思路大致如下：
- 起始时，左指针与右指针均在0。
- 开始循环右指针，每遇到一个奇数时，奇数个数加一。
- 当奇数个数等于k时，开始移动左指针，当遇到奇数时，奇数个数减一，同时结束左指针移动（此时左指针应该位于奇数右边一位）。统计左指针移动位数leftCount，将其加入返回结果。（此时区间内奇数的个数为k-1）。
- 继续移动右指针，如果遇到偶数，返回结果增加leftCount。当遇到奇数时，奇数个数加一，此时奇数个数为k，返回第3步。直到循环结束。（其实，当区间内奇数个数第一次达到k之后，随着左右指针的交替移动，区间内的奇数个数应该在k和k-1之间不停的变换。）
看下实现代码：
public int numberOfSubarrays(int[] nums, int k) {
// 左指针，每次左指针移动步数，区间内奇数个数，返回结果
int left=0, leftCount=0, oddCount=0, res=0;
for(int i=0;i<nums.length;i++){
// 如果当前为奇数，区间内奇数个数加一
if(nums[i] % 2 == 1) oddCount++;
if(oddCount==k){ // 如果奇数个数等于k
leftCount=0; // 初始化左指针移动步数
// 移动左指针直到区间内奇数个数小于k
while(oddCount==k){
leftCount++; // 左指针移动步数加一
res++; // 返回结果加一
// 当左指针遇到奇数，结束左指针移动
if(nums[left++] % 2 == 1){
oddCount--; // 区间内奇数个数减一
}
}
}else{ // 如果奇数个数小于k
// 此处应该是上一次左指针移动结束后，
// 右指针还没找到下一个奇数前。
// 或者是区间内奇数个数第一次达到k之前，
// 此时左指针还没移动过，leftCount应为0。
// 返回结果加上leftCount
res+=leftCount;
}
}
return res;
}本题解法执行时间为8ms。
Runtime: 8 ms, faster than 85.54% of Java online submissions for Count Number of Nice Subarrays.
Memory Usage: 52.9 MB, less than 100.00% of Java online submissions for Count Number of Nice Subarrays.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1248-count-number-of-nice-subarrays解题思路分析/