LeetCode161周赛第二题
1248. 统计「优美子数组」
题目描述
给你一个整数数组 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
题目分析
- 这个题目有一个坑点,就是通过答案可以看出,这里说的子数组是连续子数组
- 这样的话, 我们就可以统计到达下标x时,有多少个奇数,记为s个,求出s-k的数量(s-k>=0,<0肯定无解)即可。(前缀和的思想)
- 因为要求s-k的数量,我们不妨使用一个map来记录有 多少个下标 使得奇数个数为s,这样可以使用o(1)的时间,直接查询到我们需要的记录
Java代码
public int numberOfSubarrays(int[] nums, int k) {
int res = 0;
int s=0; // 奇数的个数
HashMap<Integer,Integer> map = new HashMap<>();
//空集合使得奇数个数为0
map.put(s,1);
for(int i=0;i<nums.length;i++){
if(nums[i]%2==1){
s++;
}
if(s-k>=0){
res +=map.get(s-k);
}
if(map.containsKey(s)){
map.put(s,map.get(s)+1);
}else{
map.put(s,1);
}
}
return res;
}