一、题目

给你一个整数数组  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

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

二、思路

  1. 建立单独的数组 odd 用于记录第 i 个奇数的坐标， [odd[i],odd[i+k−1]] 这个子数组就恰好包含 k 个奇数

  2. 子数组 [l,r] 满足 [l,r] 包含 [odd[i],odd[i+k−1] 且 [l,r] 里的奇数个数为 k 个

  3. 对于第 i 个奇数满足条件的子数组 [l,r] 的个数为：

(odd[i]−odd[i−1])∗(odd[i+k]−odd[i+k−1])

三、题解

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numberOfSubarrays = function (nums, k) {
  nums.push(1);
  const len = nums.length;
  let odd = [-1];
  let ans = 0;
  let j = 1;

  for (let i = 0; i < len; ++i) {
    const num = nums[i];
    if (num % 2) {
      odd.push(i);
      if (odd[k + 1]) {
        ans += (odd[j] - odd[j - 1]) * (odd[k + 1] - odd[k]);
        ++k;
        ++j;
      }
    }
  }
  return ans;
};

const test1 = numberOfSubarrays([1, 1, 2, 1, 1], 3);

const test2 = numberOfSubarrays([2, 4, 6], 1);

const test3 = numberOfSubarrays([2, 2, 2, 1, 2, 2, 1, 2, 2, 2], 2);

console.log('test1:', test1);
console.log('test2:', test2);
console.log('test3:', test3);