題目：統(tǒng)計(jì)「優(yōu)美子數(shù)組」
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k垄分。
如果某個(gè) 連續(xù) 子數(shù)組中恰好有 k 個(gè)奇數(shù)數(shù)字饲宛，我們就認(rèn)為這個(gè)子數(shù)組是「優(yōu)美子數(shù)組」就轧。
請(qǐng)返回這個(gè)數(shù)組中「優(yōu)美子數(shù)組」的數(shù)目险掀。
示例1:
輸入：nums = [1,1,2,1,1], k = 3
輸出：2
解釋：包含 3 個(gè)奇數(shù)的子數(shù)組是 [1,1,2,1] 和 [1,2,1,1] 沪袭。
示例2:
輸入：nums = [2,4,6], k = 1
輸出：0
解釋：數(shù)列中不包含任何奇數(shù)，所以不存在優(yōu)美子數(shù)組樟氢。
示例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
思路
- 滑動(dòng)窗口枝恋，不斷右移
right指針來擴(kuò)大滑動(dòng)窗口，使其包含k個(gè)奇數(shù) - 統(tǒng)計(jì)第一個(gè)奇數(shù)左邊的數(shù)字為
leftEvenCnt嗡害，和最后一個(gè)奇數(shù)右邊的偶數(shù)數(shù)字為rightEvenCnt焚碌。 - 最終優(yōu)美子數(shù)組的的組合數(shù)為
(leftEvenCnt + 1) * (rightEvenCnt + 1)
實(shí)現(xiàn)
func numberOfSubarrays(nums []int, k int) int {
var left, right, oddCnt, ans int
for right < len(nums) {
if nums[right]%2 == 1 {
oddCnt++
}
right++
if oddCnt == k {
tmp := right
for right < len(nums) && nums[right]%2 == 0 {
right++
}
rightEvenCnt := right - tmp
leftEvenCnt := 0
for nums[left]%2 == 0 {
leftEvenCnt++
left++
}
ans += (leftEvenCnt + 1) * (rightEvenCnt + 1)
left++
oddCnt--
}
}
return ans
}
