1248. Count Number of Nice Subarrays
給一個array nums、一個整數 k
nice subarray的定義是包含k個奇數
請問nums包含幾個 nice subarrays?
思路:
用sliding window的概念
當找到k個奇數時
就去找前後個有幾個偶數
假設前面有i個偶數、後面有j個偶數
那可以組成(i+1)*(j+1)個nice subarray
接著就扣掉第一個奇數，再去找下一個奇數
重複進行上述操作
就可以得到答案了
golang code :
func numberOfSubarrays(nums []int, k int) int {
sum,idx,l,cnt,n:=0,0,0,0,len(nums)
for idx<n{
cnt+=nums[idx]&1
if cnt==k{
prev:=l
for nums[l]&1==0{
l++
}
r:=idx+1
for r<n && nums[r]&1==0{
r++
}
sum+=(l-prev+1)*(r-idx)
l++
idx=r
cnt--
}else{
idx++
}
}
return sum
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.226.40 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719047938.A.FB6.html