力扣 1248. 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
方案一：使用前缀和配合无序映射。
func numberOfSubarrays(nums []int, k int) (ans int) {
// 定义一个无序集合， key 为前缀和，val 为达到该前缀和的数组个数
mp := make(map[int]int)
// 0 表示什么元素都不加
mp[0] = 1
// 前缀和
preSum := 0
for _, num := range nums {
// 通过 num % 2 将奇数变为 1， 偶数变为 0，方便计算
preSum += num % 2
if v, ok := mp[preSum - k]; ok {
ans += v
}
mp[preSum]++
}
return
}
- 时间复杂度：O(n)，因为需要遍历所有元素，并通过前缀和才能计算，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，因为使用了长度不超过 n 的无序映射以及常数级别的变量，所以空间复杂度为 O(n)。