題目描述:
給你一個(gè)整數(shù)數(shù)組?nums 和一個(gè)整數(shù) k蓬痒。
如果某個(gè)子數(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ù)組售担。
也就是說,我們需要從數(shù)組中統(tǒng)計(jì)出具有k個(gè)奇數(shù)數(shù)字的子數(shù)組署辉。這里子數(shù)組是連續(xù)的族铆。那么我們用一個(gè)map來記錄原數(shù)組從最左側(cè)開始的具有a個(gè)奇數(shù)的數(shù)組的數(shù)目。
比如我們給定數(shù)組:nums=[1,1,2,1,1,]哭尝。則map[0]=1,(表示為空)哥攘,map[1]=1,map[2]=1,map[3]=2,map[4]=1。
則我們下一步需要求的為子數(shù)組中含有k個(gè)奇數(shù)的子數(shù)組數(shù)目材鹦。則若當(dāng)前map[s]=a,map[s-k]=b,則此時(shí)對應(yīng)的含有k個(gè)奇數(shù)的子數(shù)組的數(shù)目為
a-b逝淹。按照這個(gè)想法很容易的就可以寫出代碼了: