原题
给你一个整数数组 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 <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
解法
思想
对于一个满足条件的最小子数组，它的左界和右界都应恰好是1，并且包含k个奇数。那么从这个最小子数组延展开，只要是偶数就可以容纳进来，可以组成的子数组个数为 左边连续偶数的个数+1 乘以 右边连续偶数的个数+1 。
代码
统计偶数间隔，这里我们统计每两个奇数之间（也可能是第一个奇数前面或最后一个奇数后面）偶数有多少个，并将它+1存放到list中，这样连续k个奇数能组成的子数组个数为数组中相隔k的两个元素的乘积：
public class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int preEven=0;
List<Integer> list=new ArrayList<>();
for(int i:nums){
if ((i&1)==0){
preEven++;
}else{
list.add(preEven+1);
preEven=0;
}
}
list.add(preEven+1);
int count=0;
for (int i=0;i<list.size()-k;i++){
count+=(list.get(i)*list.get(i+k));
}
return count;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode1248-%e7%bb%9f%e8%ae%a1%e3%80%8c%e4%bc%98%e7%be%8e%e5%ad%90%e6%95%b0%e7%bb%84%e3%80%8d/
相关推荐
-
leetcode454-四数相加II
原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。 为...
-
leetcode106-从中序与后序遍历序列构造二叉树
原题 根据一棵树的中序遍历与后序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如，给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postor...
-
剑指offer17-打印从1到最大的n位数
原题（来源Leetcode） 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入： ...
-
leetcode55-跳跃游戏
原题 原题 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入： [2,3,1...
-
leetcode402-移掉K位数字
原题 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 注意： num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 ...
-
leetcode456-132模式
原题 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak <...
-
leetcode347-前K个高频元素
原题 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例1： 输入： nums = [1,1,1,2,2,3], k = 2 输出： [1,2] 示例2： 输入： n...
-
leetcode9-回文数
原题 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 示例1: 输入： 121 输出： true 示例2: 输入： -121 输出： fa...
-
剑指offer05-替换空格
原题（来源Leetcode） 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例1: 输入： s = "We are happy." 输出： "We%20are%2...