1248. 統(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ù)組。

思路：

構(gòu)建一個(gè)奇數(shù)數(shù)組，存儲(chǔ)原數(shù)組中奇數(shù)元素的位置。
那么以第i個(gè)奇數(shù)元素 為第一個(gè)奇數(shù)元素的 子數(shù)組的個(gè)數(shù)就等于 (第i個(gè)奇數(shù)元素的下標(biāo)-第i-1個(gè)奇數(shù)元素的下標(biāo))*(第i+k個(gè)奇數(shù)元素的下標(biāo)-第i+k-1個(gè)奇數(shù)元素的下標(biāo)).
所有子數(shù)組的個(gè)數(shù)就等于把奇數(shù)數(shù)組遍歷一次所求得的和，當(dāng)沒尚未遍歷過的奇數(shù)個(gè)數(shù)小于k時(shí)，即可提前終止。

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int num = 0;
        int size = nums.size();
        int *odd = new int[size + 2]; //可能全為奇數(shù)，因此要申請(qǐng)size，又因?yàn)橐由项^尾的邊界，故size+2 。奇數(shù)元素比較少，元素總量又很多時(shí)，用vector會(huì)比較好
        memset(odd, 0, sizeof(int)*(size+2));
        int index = 0;
        for (int i = 0; i < size; ++i)
        {
            if (nums[i] & 1)  //快速判斷是否為奇數(shù)，最后一位和1相與
                odd[++index] = i; //從odd[1]開始
        }
        odd[0] = -1, odd[++index] = size; //邊界條件，根據(jù)實(shí)際加減推出
        for (int i = 1; i + k <= index; ++i) //構(gòu)造好邊界條件，可以統(tǒng)一于循環(huán)
        {
            num += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1]);
        }
        return num;
    }
};

小知識(shí)：

c++中不允許使用變量作為數(shù)組的長(zhǎng)度定義數(shù)組，當(dāng)長(zhǎng)度在運(yùn)行時(shí)才能確定，可以動(dòng)態(tài)申請(qǐng)內(nèi)存。

Type *p=new Type;
int *p=new int(2);//動(dòng)態(tài)分配一個(gè)int的空間并初始化為3

//一維數(shù)組申請(qǐng)
Type *p=new Type[n];
int *p=new int[5];
memset(p, 0, sizeof(int)*5); //初始化為0

//二維數(shù)組申請(qǐng)p[m][n];
Type **p=new Type*[m];
for(int i=0;i<m;++i)
{
    p[i]=new Type[n];
    memset(p[i], 0, sizeof(int)*n); //初始化為0
}

參考自：<https://blog.csdn.net/weixin_42638401/article/details/88957796>