统计「优美子数组」

字数 2921 2025-11-11 22:28:40

统计「优美子数组」

题目描述

给定一个正整数数组 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
解释：数组中没有奇数，所以不存在优美子数组。

解题过程

这个问题可以通过一种巧妙的转换，将其与经典的「前缀和」思想结合，从而高效解决。

问题转换与核心思路
我们关心的是子数组中奇数的个数。一个直接的想法是，我们可以遍历所有可能的子数组，并统计其中奇数的个数。但这种方法的时间复杂度是 O(n²)，对于较长的数组效率不高。
核心思路是：我们将原数组中的每个元素，根据其奇偶性，转换为一个由 0 和 1 组成的新数组。如果是奇数，我们标记为 1；如果是偶数，我们标记为 0。
例如，nums = [1, 1, 2, 1, 1] 转换为 [1, 1, 0, 1, 1]。
现在，问题就转化为：在这个由 0 和 1 组成的新数组中，有多少个子数组的和恰好为 k？
子数组的和，就是其中 1 的个数，也就是原数组中奇数的个数。
引入前缀和
为了快速计算任意子数组的和，我们使用「前缀和」技巧。
我们定义一个前缀和数组 preSum，其中 preSum[i] 表示新数组从第一个元素到第 i 个元素（索引从 0 开始）的和。
为了方便处理从第一个元素开始的子数组，我们通常会在前缀和数组前添加一个 0，表示空前缀的和。
对于转换后的数组 [1, 1, 0, 1, 1]：
preSum[0] = 0 (对应空前缀)
preSum[1] = 1 (对应 [1])
preSum[2] = 1+1 = 2 (对应 [1,1])
preSum[3] = 1+1+0 = 2 (对应 [1,1,0])
preSum[4] = 1+1+0+1 = 3 (对应 [1,1,0,1])
preSum[5] = 1+1+0+1+1 = 4 (对应整个数组)
那么，子数组从下标 i 到下标 j (i <= j) 的和，就等于 preSum[j+1] - preSum[i]。
将问题转化为两数之差
我们的目标是找到有多少对 (i, j)，使得 preSum[j+1] - preSum[i] == k。
这等价于寻找有多少对 (i, j)，使得 preSum[j+1] - k == preSum[i]。
这里，i 是子数组的起始位置的前一个位置，j 是子数组的结束位置。
使用哈希表优化查找
我们可以一边遍历数组计算当前的前缀和 currSum，一边用一个哈希表（或字典）来记录之前出现过的各个前缀和值出现的次数。
具体步骤：
a. 初始化一个哈希表 prefixCount，记录某个前缀和值出现的次数。初始时，空前缀的和为 0，所以 prefixCount[0] = 1。
b. 初始化当前前缀和 currSum = 0，以及结果计数器 count = 0。
c. 遍历数组中的每一个数字：
- 判断当前数字的奇偶性，如果是奇数，则 currSum 加 1；如果是偶数，则 currSum 不变。
- 此时，currSum 就是我们当前的前缀和 preSum[j+1]。
- 我们需要找的是，在当前位置之前，有多少个位置 i，其前缀和 preSum[i] 等于 currSum - k。因为 preSum[j+1] - preSum[i] = k。
- 这个「有多少个」就是哈希表中 prefixCount[currSum - k] 的值。我们将这个值加到结果 count 上。
- 然后，更新哈希表，将当前前缀和 currSum 的出现次数加 1（prefixCount[currSum]++），为后续的查找做准备。
逐步推演示例
以 nums = [1, 1, 2, 1, 1], k = 3 为例：
转换后数组: [1, 1, 0, 1, 1]
初始化: currSum = 0, count = 0, prefixCount = {0: 1}
- 索引 0，数字 1 (奇数):
  currSum = 0 + 1 = 1
  我们需要找 currSum - k = 1 - 3 = -2。prefixCount[-2] 不存在，为 0。count += 0 (count=0)。
  更新 prefixCount[1] = 1。现在 prefixCount = {0:1, 1:1}
- 索引 1，数字 1 (奇数):
  currSum = 1 + 1 = 2
  我们需要找 currSum - k = 2 - 3 = -1。prefixCount[-1] 不存在，为 0。count += 0 (count=0)。
  更新 prefixCount[2] = 1。现在 prefixCount = {0:1, 1:1, 2:1}
- 索引 2，数字 2 (偶数):
  currSum 不变，仍为 2。
  我们需要找 currSum - k = 2 - 3 = -1。prefixCount[-1] 不存在，为 0。count += 0 (count=0)。
  更新 prefixCount[2] 变为 2。现在 prefixCount = {0:1, 1:1, 2:2}
- 索引 3，数字 1 (奇数):
  currSum = 2 + 1 = 3
  我们需要找 currSum - k = 3 - 3 = 0。prefixCount[0] = 1。count += 1 (count=1)。
  更新 prefixCount[3] = 1。现在 prefixCount = {0:1, 1:1, 2:2, 3:1}
- 索引 4，数字 1 (奇数):
  currSum = 3 + 1 = 4
  我们需要找 currSum - k = 4 - 3 = 1。prefixCount[1] = 1。count += 1 (count=2)。
  更新 prefixCount[4] = 1。现在 prefixCount = {0:1, 1:1, 2:2, 3:1, 4:1}
最终结果 count = 2，与示例一致。

总结
这个方法的关键在于将「奇数个数」转化为「0-1数组的和」，再利用「前缀和」将子数组和问题转化为两数之差问题，最后通过哈希表记录历史前缀和来优化查找，将时间复杂度从 O(n²) 降低到了 O(n)，空间复杂度为 O(n)。这是一种非常经典且高效的处理连续子数组问题的思路。

统计「优美子数组」题目描述给定一个正整数数组 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 解释：数组中没有奇数，所以不存在优美子数组。解题过程这个问题可以通过一种巧妙的转换，将其与经典的「前缀和」思想结合，从而高效解决。问题转换与核心思路我们关心的是子数组中奇数的个数。一个直接的想法是，我们可以遍历所有可能的子数组，并统计其中奇数的个数。但这种方法的时间复杂度是 O(n²)，对于较长的数组效率不高。核心思路是：我们将原数组中的每个元素，根据其奇偶性，转换为一个由 0 和 1 组成的新数组。如果是奇数，我们标记为 1；如果是偶数，我们标记为 0。例如，nums = [ 1, 1, 2, 1, 1] 转换为 [ 1, 1, 0, 1, 1 ]。现在，问题就转化为：在这个由 0 和 1 组成的新数组中，有多少个子数组的和恰好为 k？子数组的和，就是其中 1 的个数，也就是原数组中奇数的个数。引入前缀和为了快速计算任意子数组的和，我们使用「前缀和」技巧。我们定义一个前缀和数组 preSum ，其中 preSum[i] 表示新数组从第一个元素到第 i 个元素（索引从 0 开始）的和。为了方便处理从第一个元素开始的子数组，我们通常会在前缀和数组前添加一个 0，表示空前缀的和。对于转换后的数组 [ 1, 1, 0, 1, 1 ]： preSum[0] = 0 (对应空前缀) preSum[1] = 1 (对应 [ 1 ]) preSum[2] = 1+1 = 2 (对应 [ 1,1 ]) preSum[3] = 1+1+0 = 2 (对应 [ 1,1,0 ]) preSum[4] = 1+1+0+1 = 3 (对应 [ 1,1,0,1 ]) preSum[5] = 1+1+0+1+1 = 4 (对应整个数组) 那么，子数组从下标 i 到下标 j (i <= j) 的和，就等于 preSum[j+1] - preSum[i] 。将问题转化为两数之差我们的目标是找到有多少对 (i, j)，使得 preSum[j+1] - preSum[i] == k 。这等价于寻找有多少对 (i, j)，使得 preSum[j+1] - k == preSum[i] 。这里，i 是子数组的起始位置的前一个位置，j 是子数组的结束位置。使用哈希表优化查找我们可以一边遍历数组计算当前的前缀和 currSum ，一边用一个哈希表（或字典）来记录之前出现过的各个前缀和值出现的次数。具体步骤： a. 初始化一个哈希表 prefixCount ，记录某个前缀和值出现的次数。初始时，空前缀的和为 0，所以 prefixCount[0] = 1 。 b. 初始化当前前缀和 currSum = 0 ，以及结果计数器 count = 0 。 c. 遍历数组中的每一个数字： - 判断当前数字的奇偶性，如果是奇数，则 currSum 加 1；如果是偶数，则 currSum 不变。 - 此时， currSum 就是我们当前的前缀和 preSum[j+1] 。 - 我们需要找的是，在当前位置之前，有多少个位置 i，其前缀和 preSum[i] 等于 currSum - k 。因为 preSum[j+1] - preSum[i] = k 。 - 这个「有多少个」就是哈希表中 prefixCount[currSum - k] 的值。我们将这个值加到结果 count 上。 - 然后，更新哈希表，将当前前缀和 currSum 的出现次数加 1（ prefixCount[currSum]++ ），为后续的查找做准备。逐步推演示例以 nums = [ 1, 1, 2, 1, 1 ], k = 3 为例：转换后数组: [ 1, 1, 0, 1, 1 ] 初始化: currSum = 0 , count = 0 , prefixCount = {0: 1} 索引 0，数字 1 (奇数): currSum = 0 + 1 = 1 我们需要找 currSum - k = 1 - 3 = -2 。 prefixCount[-2] 不存在，为 0。 count += 0 (count=0)。更新 prefixCount[1] = 1 。现在 prefixCount = {0:1, 1:1} 索引 1，数字 1 (奇数): currSum = 1 + 1 = 2 我们需要找 currSum - k = 2 - 3 = -1 。 prefixCount[-1] 不存在，为 0。 count += 0 (count=0)。更新 prefixCount[2] = 1 。现在 prefixCount = {0:1, 1:1, 2:1} 索引 2，数字 2 (偶数): currSum 不变，仍为 2。我们需要找 currSum - k = 2 - 3 = -1 。 prefixCount[-1] 不存在，为 0。 count += 0 (count=0)。更新 prefixCount[2] 变为 2。现在 prefixCount = {0:1, 1:1, 2:2} 索引 3，数字 1 (奇数): currSum = 2 + 1 = 3 我们需要找 currSum - k = 3 - 3 = 0 。 prefixCount[0] = 1 。 count += 1 (count=1)。更新 prefixCount[3] = 1 。现在 prefixCount = {0:1, 1:1, 2:2, 3:1} 索引 4，数字 1 (奇数): currSum = 3 + 1 = 4 我们需要找 currSum - k = 4 - 3 = 1 。 prefixCount[1] = 1 。 count += 1 (count=2)。更新 prefixCount[4] = 1 。现在 prefixCount = {0:1, 1:1, 2:2, 3:1, 4:1} 最终结果 count = 2，与示例一致。总结这个方法的关键在于将「奇数个数」转化为「0-1数组的和」，再利用「前缀和」将子数组和问题转化为两数之差问题，最后通过哈希表记录历史前缀和来优化查找，将时间复杂度从 O(n²) 降低到了 O(n)，空间复杂度为 O(n)。这是一种非常经典且高效的处理连续子数组问题的思路。