当前位置：首页 > news >正文

LeetCode 1248：统计「优美子数组」 | 前缀和与奇数计数

news 2026/6/18 4:30:20

LeetCode 1248：统计「优美子数组」 | 前缀和与奇数计数

引言

统计「优美子数组」（Count Number of Nice Subarrays）是 LeetCode 第 1248 题，难度为 Medium。题目要求找出数组中恰好有 K 个奇数的连续子数组的数量。这道题是前缀和与哈希表结合的又一个经典案例，展示了如何将"恰好 K 个奇数"的问题转化为"两个前缀和的差为 K"的问题。

这个问题的变种包括：恰好 K 个偶数的子数组、至少 K 个奇数的子数组等。核心思路都是将子数组的某种属性（前缀和）存储在哈希表中，然后查找满足条件的配对。

问题分析

题目描述

给定一个整数数组 nums 和一个整数 K，如果一个子数组中恰好有 K 个奇数，则称其为"优美子数组"。返回优美子数组的数量。

例如，输入 nums = [1,1,2,1,1,3]，K = 3，有 5 个优美子数组：

[1,1,2,1,1]（索引 0-4）
[1,2,1,1,3]（索引 1-5）
[1,1,2,1]（索引 0-3）
[2,1,1,3]（索引 2-5）
[1,2,1,1]（索引 1-4）

问题特点

这道题的核心挑战是如何高效地统计"恰好有 K 个奇数"的子数组数量。如果使用暴力枚举所有子数组，时间复杂度为 O(n²)。通过将问题转化为前缀和的差，我们可以使用哈希表在 O(n) 时间内解决。

将数组中的奇数映射为 1，偶数映射为 0，则子数组中奇数的数量等于该子数组对应元素的和。因此，"恰好有 K 个奇数"等价于"对应元素和为 K"。

前缀和解法

转换思路

将数组转换为：对于每个元素，如果是奇数则为 1，如果是偶数则为 0。这样，任意子数组的元素和就是该子数组中奇数的个数。

def numberOfSubarrays(nums, k): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num % 2 count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count

这里 num % 2 将奇数转换为 1，偶数转换为 0。prefix_map 存储每个前缀和出现的次数，初始化为 {0: 1} 表示空前缀和。

详细解析

在遍历数组时，prefix_sum 累积当前前缀和（奇数计数）。对于每个位置，prefix_sum - k 就是我们需要找的之前的前缀和。如果存在前缀和等于 prefix_sum - k 的位置，说明从那个位置到当前位置的子数组恰好有 K 个奇数。

prefix_map[prefix_sum - k] 给出了满足条件的之前位置的数量，将这个值加到 count 上，就统计了所有以当前位置结尾的优美子数组的数量。

算法正确性证明

关键引理

对于任意位置 i 和 j（j < i），子数组 nums[j+1:i] 中奇数的个数等于 prefix_sum[i] - prefix_sum[j]，其中 prefix_sum 是奇数计数的前缀和。

这个引理成立是因为 prefix_sum[i] = 奇数(nums[0:i])，prefix_sum[j] = 奇数(nums[0:j])，两者相减得到奇数(nums[j+1:i])。

正确性分析

对于每个位置 i，我们希望统计所有满足 prefix_sum[i] - prefix_sum[j] = K 的 j。对于固定的 i，满足条件的 j 就是所有使得 prefix_sum[j] = prefix_sum[i] - K 的位置。

通过在哈希表中查找 prefix_sum[i] - K，我们得到了所有满足条件的 j 的数量。将这个数量累加到 count 上，就正确统计了所有优美子数组的数量。

复杂度分析

时间复杂度

时间复杂度为 O(n)，因为只遍历数组一次，每次迭代进行常数次哈希表操作。

空间复杂度

空间复杂度为 O(n)，在最坏情况下哈希表需要存储 n+1 个不同的前缀和。

代码实现

Python 实现

def numberOfSubarrays(nums, k): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num % 2 count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count

Java 实现

public int numberOfSubarrays(int[] nums, int k) { int prefixSum = 0; int count = 0; Map<Integer, Integer> prefixMap = new HashMap<>(); prefixMap.put(0, 1); for (int num : nums) { prefixSum += num & 1; count += prefixMap.getOrDefault(prefixSum - k, 0); prefixMap.put(prefixSum, prefixMap.getOrDefault(prefixSum, 0) + 1); } return count; }

变种问题

恰好 K 个偶数

将 num % 2 改为 (num + 1) % 2 或 (num % 2) ^ 1，将偶数转换为 1，奇数转换为 0。

def numberOfSubarraysEven(nums, k): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += (num + 1) % 2 count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count

最多 K 个奇数

最多 K 个奇数的子数组数量等于"恰好 0 个奇数" + "恰好 1 个奇数" + ... + "恰好 K 个奇数"。可以遍历所有情况计算。

def atMostKSubarrays(nums, k): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num % 2 count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count

实际上，最多 K 个奇数的优美子数组就是"恰好 0 个奇数" + "恰好 1 个奇数" + ... + "恰好 K 个奇数"，可以通过累加计算。

至少 K 个奇数

至少 K 个奇数的子数组数量等于总数减去最多 K-1 个奇数的子数组数量。

测试用例

def test_number_of_subarrays(): assert numberOfSubarrays([1,1,2,1,1,3], 3) == 5 assert numberOfSubarrays([2,2,2,2,2], 0) == 10 assert numberOfSubarrays([1,1,1,1], 2) == 3 assert numberOfSubarrays([1,2,3], 1) == 2 assert numberOfSubarrays([], 0) == 1 assert numberOfSubarrays([2,2,2,1,2], 2) == 3 print("所有测试用例通过！")