leetcode1248-统计「优美子数组」

原题

给你一个整数数组 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

解法

思想

对于一个满足条件的最小子数组,它的左界和右界都应恰好是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/

发表评论

电子邮件地址不会被公开。