給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k。

如果某個(gè) 連續(xù) 子數(shù)組中恰好有 k 個(gè)奇數(shù)數(shù)字，我們就認(rèn)為這個(gè)子數(shù)組是「優(yōu)美子數(shù)組」。

請返回這個(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 <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

解題思路
找到滿足要求長度為K的數(shù)組，然后左右移動(dòng)直到碰到下個(gè)奇數(shù)為止，統(tǒng)計(jì)出滿足要求的數(shù)組個(gè)數(shù)。

舉例分析：
案列1：一個(gè)數(shù)組arr ： { 8 6 7 2 2 3 4 6 } ，其中K=2
枚舉出符合要求的子數(shù)組：
第一組：
{ 7 2 2 3 }
{ 7 2 2 3 4 }
{ 7 2 2 3 4 6 }
第二組：
{ 6 7 2 2 3 }
{ 6 7 2 2 3 4 }
{ 6 7 2 2 3 4 6 }
第三組：
{ 8 6 7 2 2 3 }
{ 8 6 7 2 2 3 4 }
{ 8 6 7 2 2 3 4 6 }

觀察規(guī)律發(fā)現(xiàn)，數(shù)組的個(gè)數(shù)由K數(shù)組左側(cè)的偶數(shù)個(gè)數(shù)m和右側(cè)的偶數(shù)個(gè)數(shù)n決定，即(m+1)*(n+1)
需要注意的是為什么+1 ，是因?yàn)?{ 7 2 2 3 }本身也可以作為起點(diǎn)和終點(diǎn)

接下來我們看案列2，稍微復(fù)雜一點(diǎn)，數(shù)組中的奇數(shù)個(gè)數(shù)大于K(k=2)：
{ 2 3 2 7 2 9 2 }
此時(shí)討論滿足需求的數(shù)組時(shí)就需要考慮在這3個(gè)奇數(shù)中進(jìn)行組合的問題了，并且左右擴(kuò)張時(shí)需要注意下個(gè)奇數(shù)的位置：
第一組：3 和7為界，共4種
{ 3 2 7}
{ 2 3 2 7}
{ 2 3 2 7 2 }
{ 3 2 7 2}
第二組：7 和 9為界，共4種
{ 7 2 9 }
{ 7 2 9 2 }
{ 2 7 2 9 }
{ 2 7 2 9 2 }
所以滿足要求的組和一共是 4 + 4 = 8

通過上面的描述，抽象出數(shù)據(jù)模式，每種子情況：
(arr[i] - arr[i-1]) * (arr[i+k] - arr[i+k-1])，其中arr是過濾之后的奇數(shù)數(shù)組。

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {

        int len = nums.length;
        int[] odd = new int[len+2];
        int index = 0;
        
        //過濾奇數(shù)，放入新數(shù)組
        for(int i=0;i<len;i++)
        {
            if((nums[i] & 1) == 1) odd[++index] = i;
        }

        //擴(kuò)充兩個(gè)邊界，方便后續(xù)i-1 和 i+1 越界問題
        odd[0] = -1;
        odd[index+1] = len;
        
        int res = 0;
        for(int i=1;i+k < index+2;i++)
        {
            res += (odd[i] - odd[i-1]) * (odd[i+k] - odd[i+k-1]);
        }

        return res;

    }
}

題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。