1. 代码段小站首页
  2. 算法

leetcode1248-统计「优美子数组」

彭晨涛 • • 算法 • 阅读 31

原题

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

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年4月20日 15:43
下一篇 2020年4月21日 14:42

相关推荐

  • leetcode837-新21点

    原题 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下： 爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一...

    彭晨涛 彭晨涛
    算法 2020年6月3日
    0100

  • 剑指offer05-替换空格

    原题（来源Leetcode） 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例1: 输入： s = "We are happy." 输出： "We%20are%2...

    彭晨涛 彭晨涛
    算法 2020年4月5日
    0100

  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...

    彭晨涛 彭晨涛
    算法 2019年12月18日
    0130

  • leetcode19-删除链表的倒数第N个节点

    原题 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为...

    彭晨涛 彭晨涛
    算法 2019年12月15日
    090
  • leetcode279-完全平方数 算法

    leetcode279-完全平方数

    原题 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出...

    彭晨涛 彭晨涛
    2019年12月11日
    0120

  • leetcode263-丑数

    原题 编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例1: 输入： 6 输出： true 解释： 6 = 2 × 3 示例2: 输入： ...

    彭晨涛 彭晨涛
    算法 2020年2月6日
    0100

  • leetcode131-分割回文串

    原题 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ...

    彭晨涛 彭晨涛
    算法 2020年5月22日
    080
  • leetcode39-组合总和 算法

    leetcode39-组合总和

    原题 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates ...

    彭晨涛 彭晨涛
    2020年5月1日
    02690

  • leetcode28-实现strStr()

    原题 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从...

    彭晨涛 彭晨涛
    算法 2019年11月20日
    0110

  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示...

    彭晨涛 彭晨涛
    算法 2019年12月29日
    070

发表回复

登录后才能评论