1248. 统计「优美子数组」

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode.cn/problems/count-number-of-nice-subarrays/
Star
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
示例 1:
输入:nums = [1,1,2,1,1], k = 3 输出:2 解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2:
输入:nums = [2,4,6], k = 1 输出:0 解释:数列中不包含任何奇数,所以不存在优美子数组。
示例 3:
输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2 输出:16
提示:
  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length
通过次数41,906提交次数73,517

法 1 滑动窗口

思路
要求 奇数 个数 刚好为 k 的 子数组数目,那么可以求 奇数个数不超过 k 的子数组数量 再减去 奇数个数不超过 k-1的子数组数量
为什么可以这么转化呢?
首先,滑动窗口在收缩的时候,奇数个数显然是不增的,所以求 奇数个数 不超过 k 的子数组数量 更直观一点。
其次,因为是求子数组,奇数个数不超过 k 的子数组一定是包括了奇数个数不超过 k-1 的子数组,所以可以通过 最差得到 奇数个数刚好为 k 的子数组数量。
题解
class Solution: def numberOfSubarrays(self, nums: List[int], k: int) -> int: return self.helper(nums, k) - self.helper(nums, k-1) def helper(self, nums, k): """奇数数字不超过 k 的子数组个数 """ wds = 0 res = 0 l, r = 0, 0 while r < len(nums): wds += 1 if nums[r] % 2 == 1 else 0 r += 1 while wds > k: wds -= 1 if nums[l] % 2 == 1 else 0 l += 1 res += r-l return res

法2 滑动窗口 技巧

思路
统计 有 k 个奇数数字 的子数字的个数。可以抽象为 长度为 k 的窗口,该窗口内固定有 k 个奇数。然后 滑动该窗口,且计算每个窗口下,子串的个数
题解
class Solution: def numberOfSubarrays(self, nums: List[int], k: int) -> int: memo = [] for i in range(0, len(nums)): if nums[i] % 2 == 1: memo.append(i) memo = [-1] + memo + [len(nums)] res = 0 for i in range(1, len(memo)-1): l = i r = i+k-1 if r < len(memo)-1: res += (memo[l]-memo[l-1]) * (memo[r+1] - memo[r]) return res