題目
給你一個整數數組 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
解釋：數列中不包含任何奇數，是以不存在優美子數組。
思路（官方題解）
這個題目中偶數其實是沒有用的，我們可以單獨建立一個odd 數組來記錄第 i個奇數的下标。那麼我們可以枚舉奇數，假設目前枚舉到第 i個，那麼 [odd[i],odd[i+k−1]] 這個子數組就恰好包含 k個奇數。由于奇數和奇數間存在偶數，是以一定存在其他子數組 [l,r]滿足 [l,r]包含 [odd[i],odd[i+k−1]] 且 [l,r]裡的奇數個數為 k個，那麼這個需要怎麼統計呢？
由于我們已經記錄了每個奇數的下标，是以我們知道對于第 i 個奇數，它的前一個奇數的下标為 odd [i−1]，也就是說(odd[i−1],odd[i]) 間的數都為偶數。同理可得(odd[i+k−1],odd[i+k]) 間的數也都為偶數。
那麼我們可以得出滿足 l∈(odd[i−1],odd[i]] 且 r∈[odd[i+k−1],odd[i+k]) 條件的子數組[l,r] 包含 [odd[i],odd[i+k−1]] 且 [l,r]裡的奇數個數為 k 個。
是以對于第 i 個奇數，它對答案的貢獻為符合條件的[l,r] 的個數，即：
(odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1])
我們隻要周遊一遍 odd 數組即可求得最後的答案，注意邊界的處理。
int numberOfSubarrays(vector<int>& nums, int k) {
int t=1;
int n = (int)nums.size();
int odd[n + 2];
for(int i=1;i<=n;i++){
if(nums[i-1]%2!=0){
odd[t++]=i-1;
}
}
int ans=0;
odd[0]=-1,odd[t++]=n;
for(int i=1;i<t-k;i++){
ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1]);
}
return ans;
}