Leetcode.1248 统计「优美子数组」

题目链接

Leetcode.1248 统计「优美子数组」 Rating ： 1624

题目描述

给你一个整数数组 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]<=1051 <= nums[i] <= 10^51<=nums[i]<=105
• $1<=k<=nums.length$

解法：前缀和 + 哈希表计数

对于 nums我们可以将 奇数看做1，偶数看做 0。

将原问题的含有 k个奇数转换成 区间和为 k的数量。

我们用 s表示这样的前缀和。

如果一个区间 [ l , r ]是 s[j] - s[i-1] == k，该区间就是一个合法区间。我们只需要记录这样的合法区间的数量即可。

用 哈希表 m来存储每一个前缀和 s[i]的出现次数。

时间复杂度： $O(n)$

C++代码：

class Solution {
public:int numberOfSubarrays(vector<int>& nums, int k) {int n = nums.size();vector<int> s(n+1);for(int i = 1;i <= n;i++) s[i] = s[i - 1] + (nums[i-1] & 1);int ans = 0;unordered_map<int,int> m;for(auto x:s){ans += m[x - k];m[x]++;}return ans;}
};

Python代码：

class Solution:def numberOfSubarrays(self, nums: List[int], k: int) -> int:n = len(nums)s = [0] * (n + 1)for i in range(1,n + 1):s[i] = s[i-1] + (nums[i-1] & 1)ans = 0m = Counter()for x in s:ans = ans + m[x - k]m[x] = m[x] + 1return ans