1248_统计「优美子数组」

难度：中等

题目

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。

示例

示例一：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例二：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例三：

输入：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

解题

可以用滑动窗口的方法

  • 当 odd 不等于 k 的时候，移动右边界；

  • 当 odd 等于 k 的时候，记录右边界位置，然后寻找右边界右边偶数的数量，移动左边界，寻找左边界右边偶数的数量，结果 += 右边界*左边界。然后左边界右移一位，odd减一，继续循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int ans = 0, left = 0, right = 0, odd = 0;
        while (right<nums.length){
            if (nums[right++]%2==1){
                odd++;
            }
            if (odd==k){
                int temp = right;
                while (right<nums.length&&(nums[right]%2==0)){
                    right++;
                }
                int rightCount = right - temp;
                int leftCount  = 0;
                while (nums[left]%2==0){
                    leftCount++;
                    left++;
                }
                ans += (leftCount+1)*(rightCount+1);
                left++;
                odd--;
            }
        }
        return ans;
    }
}

也可以采用前缀和的方法，可大大降低时间复杂度

计算前缀和数组 count，对于每个元素，计算当前的前缀和（到当前元素位置，数组中有多少个奇数）。然后双重循环统计 count[j] - count[i] == k 的个数。此时时间复杂度为 $O(N^2)$

可以利用 HashMap 降低时间复杂度，key 是 前缀和，value 是前缀和的个数，遍历原数组，每遍历一个数组，计算前缀和 sum，然后结果累加前缀和为 sum - k 的个数。（这里使用数组来记录，数组下标为前缀和，值为前缀和的个数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int ans = 0;
        int len = nums.length;
      	// 下标为前缀和（奇数的个数）, 值为此前缀和出现的次数
        int[] count = new int[len+1];
      	// 处理前缀和刚好等于 k 的情况
        count[0] = 1;
        int sum = 0;
        for(int num:nums){
          // 计算前缀和更新到数组中
            sum+=num&1;
            count[sum]++;
          // 符合条件 就在结果中累加
            if(sum>=k){
                ans+=count[sum-k];
            }
        }
        return ans;
    }
}