echo

任生命穿梭 时间的角落

0%

统计「优美子数组」

Posted on In Valine:

1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：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 数组来记录第 i 个奇数的下标，假设当前枚举到第 i 个，那么 [odd[i], odd[i+k-1]] 这个子数组恰好包含 k 个奇数。这个范围左侧的奇数下标为 odd[i-1], 右侧的奇数下标为 odd[i+k]。如果[odd[i], odd[i+k-1]] 这个包含 k 个奇数的子数组左右侧都右偶数，那么满足条件的包含 k 个奇数的子数组个数为 (odd[i]−odd[i−1])∗(odd[i+k]−odd[i+k−1]) 。我们只要遍历一遍 odd 数组即可求解答案。

边界处理：

  1. 当 nums[0] 为奇数时，odd[1] = 0，此时左边没有偶数 odd[1] - odd[0] 应该为 1（只有 nums[0] 为子数组左侧边界）。此时 odd[0] = -1。
  2. 当记录最后一个奇数时（假设这是第 index 个奇数，对应 nums 数组中的下标为 x）， odd[index] = x, odd[index+1] = nums.length。odd 数组最后一个元素记录的是数组中所有元素的数量。

以示例 3 来解释：我们生成的 odd 数组为 [-1, 3, 6, 10]，对其遍历一遍得到结果 (3 - (-1)) * (10-6) = 16。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] odd = new int[n+2];
        int index = 0, ans = 0;
        
        //生成 odd 数组
        for(int i=0 ; i < n; ++i){
            if( (nums[i] & 1) == 1)odd[++index] = i;
        }
        //边界处理
        odd[0] = -1; odd[++index] = n;
		//计算结果
        for(int i=1; i+k <= index; ++i){
            ans += (odd[i] - odd[i-1])*(odd[i+k] - odd[i+k-1]);
        }
        return ans;
    }
}

时间复杂度O(n)，空间复杂度O(1)。