[python 刷题] 1248 Count Number of Nice Subarrays

[python 刷题] 1248 Count Number of Nice Subarrays

题目如下：

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

这道题和 1343 Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold 挺像的

双指针

先声明，我的写法不是最有效的，其他的双指针/滑动窗口的解法会更加的高效，不过我感觉对我来说这么写是最好理解的

首先题目要求必须要有 k 个奇数，以题目中 Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2 为例，它的 base case 是这样的：

同时，因为两边都是偶数，因此指针是可以向两边延长的，演唱后也都是满足题目需求，即，子数组中有 k 个奇数

首先用两个指针指向 $l$ 和 $r$，使用 $counter$ 计算 $[l,l+1,...,r]$ 中的奇数。每次移动 $r$ 的时候，更新 $counter$，这时候会出现两个需要照顾的条件：

1. $counter>k$

   这个时候就需要不断移动 $l$，一直到 $counter==k$

2. $counter==k$

   依旧以上面的案例来说，因为左侧指针没有动过，实际上应该是这样的情况：

   

   这时候新建一个 $temp$ 指针代替右侧指针，并且将 $diff$ 保存下来：

   

   这里的 $diff$ 代表着不同的组合，即 $l$ 移动一格时所会产生的不同组合，在移动左侧指针时，每次添加 $diff$ 即可

代码如下：

class Solution:def numberOfSubarrays(self, nums: List[int], k: int) -> int:n = len(nums)res, count = 0, 0l, r = 0, 0while r < n:if nums[r] % 2:count += 1while count > k:if nums[l] % 2:count -= 1l += 1if count == k:res += 1t = r + 1while t < n and not nums[t] % 2:res += 1t += 1diff = t - rr = t - 1while l < r and not nums[l] % 2:res += diffl += 1r += 1return res

prefix sum

使用 prefix sum 就比较简单了，这里是将所有出现奇数的次数全都保存下来到一个变量中，同时，会形成一个 {odd_num: even_num_freq + 1} 的对应关系，这样可以保存不同的组合

如 Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2，它的键值对的关系为 {0: 4, 1: 3, 2: 4}，其中保存的对应关系为：

0: [default_value, 2,2,2]
1: [1,2,2]
2: [1,2,2,2]

这样，通过 count[odd_count - k] 就能够获取对应的变化，也就是上一个解法中的 $diff$，代码如下：

class Solution:def numberOfSubarrays(self, nums: List[int], k: int) -> int:n = len(nums)# 这里使用数组而非字典，不过其原理是一样的# 使用 n + 1 是因为 0 为没有出现 odd 的情况# 而当数组中所有的成员都是 odd 时，count 的长度就为 n + 1count = [0] * (n + 1)# 这个是 base case# 空数组也是一个合法的 subarraycount[0] = 1odd_count = 0res = 0for num in nums:if num % 2 == 1:odd_count += 1if odd_count >= k:res += count[odd_count - k]count[odd_count] += 1return res