https://leetcode-cn.com/problems/count-number-of-nice-subarrays/ 双指针

前缀和 差分

  1. function numberOfSubarrays(nums: number[], k: number): number {
  2.    let n = nums.length
  3.    // @ts-ignore
  4.    let counts = new Array(n + 1).fill(0).fill(1,0,1)
  5.    let oddCount = 0
  6.    let result = 0
  8.    for (let i = 0; i < n; i++) {
  9.       oddCount += nums[i] & 1
  10.       result += oddCount >= k ? counts[oddCount - k] : 0
  11.       counts[oddCount] += 1
  12.    }
  13.    return result
  14. };

滑动窗口

function numberOfSubarrays(nums: number[], k: number): number {
   let left = 0
   let right = 0
   let oddCount = 0
   let res = 0

   while (right < nums.length) {
      // 右指针先走，每遇到一个奇数则 oddCount++
      oddCount += (nums[right++] & 1)

      // 若当前滑动窗口 [left, right) 中有 k 个奇数，进入此分支统计当前滑动窗口中的优美子数组个数
      if (oddCount === k) {
         // 先将滑动窗口的右边界向右扩展，直到遇到下一个奇数或出界
         // rightEventCnt 即为第 k 个奇数右边的偶数个数
         let temp = right
         while (right < nums.length && !(nums[right] & 1)) {
            right++
         }
         let rightEventCnt = right - temp

         // leftEventCnt 即为第一个奇数左边的偶数的个数
         let leftEventCnt = 0
         while (!(nums[left] & 1)) {
            leftEventCnt++
            left++
         }

         // 第 1 个奇数左边的 leftEvenCnt 个偶数都可以作为优美子数组的起点
         // (因为第1个奇数左边可以1个偶数都不取，所以起点的选择有 leftEvenCnt + 1 种）
         // 第 k 个奇数右边的 rightEvenCnt 个偶数都可以作为优美子数组的终点
         // (因为第k个奇数右边可以1个偶数都不取，所以终点的选择有 rightEvenCnt + 1 种）
         // 所以该滑动窗口中，优美子数组左右起点的选择组合数为 (leftEvenCnt + 1) * (rightEvenCnt + 1)
         res += (leftEventCnt + 1) * (rightEventCnt + 1)

         // 此时 left 指向的是第一个奇数，因为该区间已经统计完了，因此 left 右移一位，oddCnt--
         left++
         oddCount--
      }
   }

   return res
};