优美子数组¶

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

题解¶

这道题和Least-K子数组可以相互联系。

Least-K子数组是要找某个数字至少出现k次的子数组（换言之就是k, k+1, k+2 ...都可以）。我们这里是要找恰好出现k次。

那么显然有：

exactly_k = least_k - least_{k+1}

这个技巧非常好用！！！

或者，对称地我们有：

exactly_k = most_k - most_{k-1}

Least K¶

几乎直接照搬Least-K子数组的代码即可，只需要稍微修改条件：

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def least_k(k):
            """k, k+1, k+2, ..."""
            n = len(nums)
            res = curr = right = 0
            for num in nums: # 遍历左指针
                # 移动右指针【不包含】，直到子数组满足条件（或者数组到头了
                while right < n and curr < k:
                    curr += (nums[right] % 2 == 1)
                    right += 1
                # 如果移动到头还是不满足条件，就结束
                if curr < k:
                    break
                # 否则，curr = k，这时候我们找到了一个子数组nums[左指针: 右指针]可以满足条件
                # 那么右指针往右都是满足（至少k个）的条件的
                res += n - right + 1
                # 每次移动左指针都要更新当前子数组的状态
                curr -= (num % 2 == 1)
            return res
        return least_k(k) - least_k(k+1)

Most K¶

Most K和Least K的代码思路几乎一致，也是用双指针：

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def most_k(k):
            """1, 2, ..., k-1, k"""
            left = right = res = curr = 0
            # 遍历右侧指针
            while right < len(nums):
                curr += nums[right] % 2 == 1
                # 右指针到位了之后
                # 移动左指针
                while curr > k and left <= right:
                    curr -= nums[left] % 2 == 1
                    left += 1
                right += 1
                # 所有子数组
                res += right - left
            return res
        return most_k(k) - most_k(k-1)

前缀和¶

这题还可以使用前缀和，来实现空间换时间。

定义：

前缀和current：到目前的位置，已经遇到了多少奇数
前缀和字典freq{x:y}：此前，此前有y个前缀子数组，恰好有x个奇数

那么我们每次想要找恰好k个奇数的子数组，个数为freq[current - k]。

代码如下：

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        freq = defaultdict(int)
        freq[0] = 1  # 前缀和字典，k:v 此前有v个前缀子数组，恰好有k个奇数
        current = 0  # 当前窗口内有多少个奇数
        res = 0
        for num in nums:
            if num % 2 == 1:
                current += 1  # 更新前缀和
            need = current - k  # k = current - need，前缀和相减就是它们之间的子数组
            res += freq.get(need, 0) 
            # ！！！不能先更新前缀和字典再更新res
            # 否则 k==0 的时候会重复计算
            # 这种情况下 need == current
            # 其他情况不影响
            freq[current] += 1  # 记录前缀和
        return res

单指针¶

实际上这题还有更简单的解法。

注意到子数组实际上只和奇数出现的位置相关。

例如[1,1,2,1,1,2,2]这个数组，奇数出现的位置是[0,1,3,4]。

那么我们可以直接从奇数出现的这些位置计算出满足条件的子数组的个数。

考虑k=3的情况。那么子数组就必须包含[0,1,3,4]中的3个元素，只有两种情况：

[0,1,3]
[1,3,4]

满足这个条件的子数组分别是：

[0,1,3]
- nums[0:4]
[1,3,4]
- nums[1:5],nums[1:6],nums[1:7]

从上述过程我们可以提取出一种直接的计算方法：

只要寻找指针[x:y]恰好包含了k个奇数，然后再计算指针可以滑动的范围之积即可：

res += span_x * span_y