问题描述

给定一个整数数组 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 <= 50000
1 <= nums[i] <= 10^5
1 <= 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
};