LEETCODE 1248. Count Number of Nice Subarrays解题思路分析

题目大意:

统计「优美子数组」

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1248

解题思路分析:

本题这种寻找连续区间的题目,很容易想到使用Sliding Window来解题。即找到所有的区间[i, j],保证在区间内存在k个奇数即可。对于如何找到所有区间,我们来举例说明,比如存在以下数组,并且k为1:

int nums = [2, 4, 3, 6, 8];
int k = 1;

很显然,数组中只有1个奇数3,其他均为偶数,先看3的左边,存在2个偶数,这两个偶数与3能组成3个子数组:

int nums = [2, 4, 3, 6, 8]; // 原数组

int sub1 = [3]; // 1个奇数自己组成的子数组
int sub2 = [4, 3]; // 加入4
int sub3 = [2, 4, 3]; // 加入2

再看奇数3的右边,也存在2个偶数,因为左边存在3个子数组,因此每次向左边的子数组中加入一个数字,子数组的个数都会加3,比如,先加入6:

int nums = [2, 4, 3, 6, 8]; // 原数组

int sub4 = [3, 6]; // 加入6
int sub5 = [4, 3, 6]; // 加入6
int sub6 = [2, 4, 3, 6]; // 加入6

接下来再加入8:

int nums = [2, 4, 3, 6, 8]; // 原数组

int sub7 = [3, 6, 8]; // 加入8
int sub8 = [4, 3, 6, 8]; // 加入8
int sub9 = [2, 4, 3, 6, 8]; // 加入8

一共产生了9个子数组:

int sub1 = [3]; // 1个奇数自己组成的子数组
int sub2 = [4, 3]; // 加入4
int sub3 = [2, 4, 3]; // 加入2

int sub4 = [3, 6]; // 加入6
int sub5 = [4, 3, 6]; // 加入6
int sub6 = [2, 4, 3, 6]; // 加入6

int sub7 = [3, 6, 8]; // 加入8
int sub8 = [4, 3, 6, 8]; // 加入8
int sub9 = [2, 4, 3, 6, 8]; // 加入8

由此我们可以得到一个规律,在奇数左边加上一个偶数,可以得到一个新的子数组,在奇数右边加上一个偶数,可以得到n个新的子数组(n为左边子数组的个数)。

这里也可以换一种思考方式,奇数与左边的2个偶数可以组成3个子数组,同理,奇数与右边的2个偶数也可以组成3个子数组,因此,总的组合数为左右两边的个数相乘,即3乘以3等于9。

所以解题思路大致如下:

  1. 起始时,左指针与右指针均在0。
  2. 开始循环右指针,每遇到一个奇数时,奇数个数加一。
  3. 当奇数个数等于k时,开始移动左指针,当遇到奇数时,奇数个数减一,同时结束左指针移动(此时左指针应该位于奇数右边一位)。统计左指针移动位数leftCount,将其加入返回结果。(此时区间内奇数的个数为k-1)。
  4. 继续移动右指针,如果遇到偶数,返回结果增加leftCount。当遇到奇数时,奇数个数加一,此时奇数个数为k,返回第3步。直到循环结束。(其实,当区间内奇数个数第一次达到k之后,随着左右指针的交替移动,区间内的奇数个数应该在k和k-1之间不停的变换。)

看下实现代码:

public int numberOfSubarrays(int[] nums, int k) {
    // 左指针,每次左指针移动步数,区间内奇数个数,返回结果
    int left=0, leftCount=0, oddCount=0, res=0;
    for(int i=0;i<nums.length;i++){
        // 如果当前为奇数,区间内奇数个数加一
        if(nums[i] % 2 == 1) oddCount++;
        if(oddCount==k){ // 如果奇数个数等于k
            leftCount=0; // 初始化左指针移动步数
            // 移动左指针直到区间内奇数个数小于k
            while(oddCount==k){
                leftCount++; // 左指针移动步数加一
                res++; // 返回结果加一
                // 当左指针遇到奇数,结束左指针移动
                if(nums[left++] % 2 == 1){
                    oddCount--; // 区间内奇数个数减一
                }
            }
        }else{ // 如果奇数个数小于k
            // 此处应该是上一次左指针移动结束后,
            // 右指针还没找到下一个奇数前。
            // 或者是区间内奇数个数第一次达到k之前,
            // 此时左指针还没移动过,leftCount应为0。
            // 返回结果加上leftCount
            res+=leftCount;
        }
    }
    return res;
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 85.54% of Java online submissions for Count Number of Nice Subarrays.

Memory Usage: 52.9 MB, less than 100.00% of Java online submissions for Count Number of Nice Subarrays.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1248-count-number-of-nice-subarrays解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。