问题描述
给定一个整数数组 nums 和一个整数 k。当子数组中有 k 个奇数时，称之为 nice。
要求返回 nice 子数组的个数。
栗 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
解题思路
题目要求子数组中只需包含 k 个奇数，因此其可以与任意个数的偶数进行组合。
同时 k 个奇数不一定是连续的，有可能掺杂着偶数。由于子数组的连续性， k 个奇数之间的偶数是必须包含的。当我们找到 k 个奇数时，需要考虑其与前后偶数的组合性。
举个栗子，比如 nums = [2, 2, 1, 2, 3, 4, 6, 8], k = 2。
子数组中需包含 2 个奇数，该数组中奇数为 1、3。显然， [1, 2, 3] 是子数组中必须要包含的元素。而左边的偶数 [2, 2] 和右边的偶数 [4, 6, 8] 则是可选的。它们的组合情况如下：
- 左边有
[], [2], [2, 2]三种组合。 - 右边有
[], [4], [6], [4, 6, 8]四种组合。
因此，左右两两组合总数为 3 * 4 = 12 。
稍微观察一下，我们可以发现：当有 n 个偶数时，组合数为 n + 1。因此，转换下思路，只需要求出左右两边偶数的个数即可。
而如何求得偶数个数呢？也比较简单，通过记录两个相邻奇数的下标，相减即可。但有种边界情况需要考虑：第一个出现的奇数，它前面没有奇数；最后一个出现的奇数，它后面有没奇数。
还是拿上面的栗子说明。
- 第一个奇数
1的下标是2，可默认前一个奇数下标为0，那么偶数个数为2 - 0 = 2。 - 最后一个奇数
3的下标是4，可默认最后一个奇数下标为数组长度 - 1，那么偶数个数为7 - 4 = 3。
当然，k 个奇数的组合方式可能不止一种，那么就需要遍历每 k 个奇数，求出它与偶数的组合数，最终得到总的组合数。
比如 nums = [2, 2, 1, 2, 3, 4, 5, 6], k = 2，奇数为 1、3、5。那么 k 个奇数的可能取值为 1、3、3、5，这里需要分别计算出它们与偶数的组合数。
注意：当取 1、3 时，由于它后面还有一个奇数 5，因此计算右边偶数个数时，只需计算到 5 的位置。
总体思路如下：
- 首先取出 k 个奇数，假设其起始下标为
[m, n]。 - 将 m 与左边相邻的奇数下标做计算，求出左边组合数个数
left。 - 将 n 与右边相邻的奇数下标做计算，求出右边组合数个数
right。 - 左右两边组合数相乘，即为这个 k 个奇数的组合数：
left * right。 - 向后遍历，继续取出 k 个奇数，重复以上步骤。即始终保持 k 个奇数的窗口，不断向后移动。
解法 1
这种解法比较容易理解，就是上面阐述的思路。
- 遍历数组，记录所有奇数的下标。
- 遍历下标列表，分别求出 k 个奇数左右两边的组合数，然后相乘。
- 注意考虑第一个奇数和最后一个奇数的情况。
代码如下：
var numberOfSubarrays = function (nums, k) {
if (!nums) {
return 0;
}
let sum = 0;
// 奇数的 index 列表
let oddList = [];
nums.forEach((element, index) => {
if (element % 2 === 1) {
oddList.push(index);
}
});
let i = 0;
while (i <= oddList.length - k) {
let left = 0;
let right = 0;
// 计算左边的组合数，从原数组第一个数开始
if (i === 0) {
left = oddList[i] + 1;
} else {
// 计算相邻的个数
left = oddList[i] - oddList[i - 1];
}
// 覆盖 k 个奇数
// 计算右边的组合数
const endIndex = i + k - 1;
// 最后一个，组合个数可一直到原数组末尾
if (endIndex == oddList.length - 1) {
right = nums.length - oddList[endIndex];
} else {
// 计算相邻的个数
right = oddList[endIndex + 1] - oddList[endIndex];
}
sum += left * right;
i += 1;
}
return sum;
};
解法 2
思路上大同小异，只不过不需要事先计算出奇数下标列表，而是在遍历过程中判断是否达到了 k 个奇数的条件。如果满足条件，则计算组合数；如果超过了 k 个奇数，则需更新 k 个奇数列表，再进行计算。
以下代码是采用记录开始窗口的下标，然后不断滑动窗口更新下标的方式。也可以采用操作窗口数组的方式，当元素个数大于 k 时，删除第一个元素，让其始终保持 k 个数。
js 代码如下：
var numberOfSubarrays = function (nums, k) {
if (!nums) {
return 0;
}
let sum = 0;
// 记录上一次 k 个奇数数的第一个数下标
let oddIndex = 0
// 奇数的 index 列表，默认填入 -1
let oddList = [-1];
nums.forEach((element, index) => {
if (element % 2 === 1) {
oddList.push(index)
// 当已经有 k 个奇数，更新记录下标
if (oddList.length - oddIndex - 1 > k) {
oddIndex += 1
}
}
// 满足 k 个奇数
if (oddList.length - oddIndex - 1 === k) {
sum += oddList[oddIndex + 1] - oddList[oddIndex]
}
});
return sum
};
