LeetCode1248. 统计「优美子数组」

1. 题目 给你一个整数数组 nums 和一个整数 k。 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 请返回这个数组中「优美子数组」的数目。 示例 1： 输入：nums = [1,1,2,1,1], k = 3 输出：2 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 2. 解题思路 在LeetCode第1248题“统计'优美子数组'”中，我们需要找到一个整数数组`nums`中所有连续子数组，这些子数组恰好包含`k`个奇数。这里的子数组是连续的，这意味着相邻的元素是连续考虑的。目标是返回满足条件的优美子数组的数量。 我们要理解解题的关键在于如何有效地计算每个优美子数组。这个问题可以通过维护两个奇数计数器来解决：一个是当前奇数的数量，另一个是之前遇到的偶数数量。这是因为当我们在数组中移动时，只有奇数和奇数之间的偶数个数会影响优美子数组的数量。 解题思路如下： 1. 初始化两个字典：`count_odd`和`count_odd_right`。`count_odd`用于存储遍历过程中遇到的奇数个数及其对应的左侧偶数个数，`count_odd_right`则存储遍历过程中遇到的奇数个数及其对应的右侧偶数个数。 2. 遍历数组`nums`，计算当前奇数和偶数的累计个数，并更新`count_odd`字典。如果遇到奇数，将左侧偶数个数（`even - lasteven`）保存到`count_odd`中，`lasteven`记录上一个奇数后的偶数个数。 3. 反向遍历数组，计算每个位置的奇数个数及其右侧偶数个数，更新`count_odd_right`字典。同样，如果遇到奇数，将右侧偶数个数（`even - lasteven`）保存到`count_odd_right`中。 4. 对`count_odd`的键进行排序，然后对于每个键`i`，计算其左侧偶数个数（`left`）和键`i+k-1`在`count_odd_right`中的右侧偶数个数（`right`）。将这两个值相乘并累加到结果`res`中。 5. 返回结果`res`作为优美子数组的数量。 代码实现中，`count_odd`和`count_odd_right`字典分别用于记录奇数个数及其相邻偶数个数的信息。在正向遍历和反向遍历过程中，通过`even`变量跟踪当前的偶数个数，`lasteven`变量保持前一个奇数之后的偶数个数。通过遍历`count_odd`的键，与`count_odd_right`配合计算优美子数组的总数。 在示例1中，输入数组`nums = [1,1,2,1,1]`，`k = 3`。有两个优美子数组：`[1,1,2,1]`和`[1,2,1,1]`，因为它们都包含恰好3个奇数。通过上述方法，我们可以正确地计算出这两个优美子数组。 这个题目考察了动态规划和字典数据结构的应用，以及如何在数组中有效地查找和计算满足特定条件的子序列。在实际编程中，这样的技巧经常用于解决涉及计数和子数组的问题。