每天一道leetcode(Day 25)

1248. 统计「优美子数组」

题目描述

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

解题思路

• 参考官方题解灵感，使用动态规划解决此问题(解法很妙，还需琢磨)

• 明确状态：dp[i] 表示 0..i 中奇数的个数;

• 确定状态转移方程：

  • dp[i] 与 dp[i-1] 的关系为： dp[i] = dp[i-1] + (nums[i] & 1)，&表示按位与，只有 num[i]是奇数时 nums[i] & 1 值为 0，否则为 1；
  • 题目要求的是符合 k 个奇数的子数组的个数，则假设存在一个子数组 j..i 满足：dp[i] - dp[j-1] === k，也就是从 i 到 j-i 中间有 k 个奇数；
  • 将上一步的等式转换过来就是 dp[j-1] === dp[i] - k（题目的要求就可以转化为统计一下有多少个奇数个数为 dp[i] - k 的 dp[j] 即可）
  • 建立 counts 数组来记录 dp[i] 出现的次数，则要求的 counts[dp[j]] 就等于 counts[dp[i] - k]
  • 因为 dp[i] 只与 dp[i-1] 有关，所以可以状态压缩为变量 oddCount 即可
    即 result += counts[oddCount - k]

• 初始情况：
  counts[0] = 1

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numberOfSubarrays = function (nums, k) {
  // fill(value,start,end)=>fill(1, 0, 1)
  let n = nums.length,
    counts = new Array(n + 1).fill(0).fill(1, 0, 1),
    oddCount = 0,
    result = 0;
  for (let i = 0; i < n; i++) {
    oddCount += nums[i] & 1;
    result += oddCount >= k ? counts[oddCount - k] : 0;
    counts[oddCount] += 1;
  }
  return result;
};

参考

1248. 统计「优美子数组」