LeetCode 1248. 统计「优美子数组」

2024-04-19 HGNULB 约 10 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 1248. 统计「优美子数组」

题意分析

给一个整数数组 nums 和整数 k，若某个连续子数组中恰好有 k 个奇数，就称它「优美」。要统计优美子数组的个数。

第一件要看穿的事：题目只在乎「是奇是偶」，元素的具体数值毫无用处。所以可以先在脑子里把数组映射成 0/1 序列——奇数记 1、偶数记 0。问题立刻变成：在一个 0/1 数组中，有多少个连续子数组的和恰好等于 k。这个转化把一道看起来很特殊的题归到了一个非常大的题族里。

第二件事是「恰好等于」这个措辞。它和「不超过」「至少」是三种不同的形态：「不超过」有单调性可以直接双指针；而「恰好」在一般数组上没有单调性，标准工具是前缀和之差——子数组 (i, j] 的奇数个数等于「前 j 个的奇数个数」减「前 i 个的奇数个数」。于是问题变成统计有多少对下标满足两个前缀值相差 k。

第三件事是「求个数」而不是「求某个最值」。求个数意味着不能只保留每个前缀值的一个代表，必须记录每个前缀值出现了多少次——不同的出现位置对应不同的左端点，都要计入。

约束方面：n ≤ 5 × 10^4，$O(n^2)$ 的双重循环大约 $2.5 \times 10^9$ 次，会超时，需要线性解法。另外注意前缀奇数个数的取值范围是 0..n，是一段连续的小整数，这意味着可以用数组代替哈希表来计数，常数更小。

边界：k 可能大于数组中奇数的总数，此时答案为 0；数组可能全是偶数；子数组两端可以带任意多个偶数，所以同一组奇数会对应多个不同的子数组，这正是计数的来源。

解法：前缀奇数个数计数

核心思路

暴力做法是枚举左右端点，对每个区间数一遍奇数个数，$O(n^3)$；稍作优化，固定左端点后向右扩并增量维护计数，降到 $O(n^2)$。瓶颈在于对每个右端点都要重新遍历所有左端点。

记 odd[j] 为前 j 个元素中奇数的个数（odd[0] = 0）。那么以下标 j - 1 结尾、以下标 i 开头的子数组，其奇数个数正是 odd[j] - odd[i]。「恰好 k 个奇数」等价于 odd[i] = odd[j] - k。

于是问题被彻底改写：从左往右扫描，每到一个右端点 j，答案要加上此前已经出现过多少个前缀值等于 odd[j] - k。只要边扫边用一张计数表记录每个前缀值出现的次数，每个右端点就只需一次查表，总代价降到 $O(n)$。这就是「和为 K 的子数组」那一族题的统一骨架。

循环不变量：在处理右端点 j（即刚把 nums[j-1] 计入 oddCount 之后、把 oddCount 写入计数表之前），prefixCount[v] 恰好等于「在 0..j-1 这些更早的前缀位置中，前缀奇数个数等于 v 的位置数量」。有了这条不变量，prefixCount[oddCount - k] 就精确等于「以当前位置为右端点的优美子数组个数」，累加即得全局答案。

维持不变量的关键是先查询后写入：如果先把当前 oddCount 计进表里再去查，当 k = 0 时 oddCount - k 就是 oddCount 自己，会把「长度为 0 的空子数组」也算进去，答案偏大。

另一个必要的初始化是 prefixCount[0] = 1，它代表「前缀位置 0」这个虚拟的空前缀。没有它，所有从数组第一个元素开始的优美子数组都会被漏掉——因为它们对应的左端前缀值正是 0。

最后一个选择是用数组而不是哈希表做计数。前缀奇数个数只可能落在 [0, n] 这段连续区间里，直接开一个长度 n + 1 的 int 数组，读写都是 $O(1)$ 且无哈希开销，比 HashMap 快得多，代码也更短。这是「键是有界小整数」时的标准优化。

解题步骤

开一个长度为 n + 1 的计数数组，并置 prefixCount[0] = 1。长度为什么是 n + 1：前缀奇数个数最大就是全数组都是奇数时的 n，下标要能取到 n。初值 1 为什么必须有：它代表空前缀，是所有「从头开始」的子数组的左边界来源。

从左到右遍历，遇到奇数就 oddCount++。为什么偶数什么都不做：偶数不改变奇数计数，但它仍然会让「前缀位置」增加一个——这一点由后面的「无条件写入计数表」来体现。

先查询：若 oddCount >= k，把 prefixCount[oddCount - k] 累加进答案。为什么要有 oddCount >= k 这道判断：oddCount - k 为负时下标越界；而且负值在语义上表示「需要一个不可能存在的前缀」，其贡献本来就是 0，跳过即可。

后写入：prefixCount[oddCount]++。为什么必须放在查询之后：k = 0 时查询的正是 oddCount 自己，先写入会把当前位置与自身配对，凭空多出一个长度为 0 的「子数组」。同时注意这一步是无条件执行的——哪怕当前元素是偶数、oddCount 没变，也要再计一次，因为它是一个新的前缀位置，能充当新的左端点。这正是「一组奇数外面裹着不同数量的偶数会产生多个子数组」的计数机制。

返回累加结果。遍历结束时每个右端点都被处理过一次，由不变量可知每次累加的都是以该位置结尾的优美子数组个数，求和即为全局答案。

以 nums = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2]、k = 2 走一遍（答案是 16）。奇偶映射后是 [0,0,0,1,0,0,1,0,0,0]。

初始：prefixCount = [1, 0, 0, ...]，oddCount = 0，ans = 0。

前三个元素都是偶数：oddCount 保持 0；每次查询因 0 >= 2 不成立而跳过；每次写入让 prefixCount[0] 依次变成 2、3、4。此时 prefixCount[0] = 4，含义是「奇数个数为 0 的前缀位置」有 4 个（空前缀 + 前 1、2、3 个元素），它们都是潜在的左端点。

第 4 个元素 1：oddCount = 1；1 >= 2 不成立，跳过查询；prefixCount[1] 变成 1。

第 5、6 个元素都是偶数：oddCount 仍为 1；查询仍跳过；prefixCount[1] 依次变成 2、3。

第 7 个元素 1：oddCount = 2；查询 prefixCount[2 - 2] = prefixCount[0] = 4，ans = 4。这 4 个正是以第 7 个元素结尾、左端分别从下标 0、1、2、3 开始的四个子数组，它们都恰好含 1 和 1 这两个奇数。然后 prefixCount[2] 变成 1。

第 8、9、10 个元素都是偶数：oddCount 保持 2；每次查询都得到 prefixCount[0] = 4，ans 依次变成 8、12、16；同时 prefixCount[2] 依次变成 2、3、4。这三轮体现了「右端多裹几个偶数也仍然优美」。

遍历结束，返回 16。

顺带验证两个细节：若漏掉 prefixCount[0] = 1 的初始化，prefixCount[0] 全程少 1，每次查询少算一个，答案会变成 12；若把写入放到查询之前，本例 k = 2 时恰好看不出差别，但换成 k = 0（如 nums = [2, 2]、k = 0，正确答案 3）就会多算出 2 个空子数组，返回 5。

代码实现

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int[] prefixCount = new int[nums.length + 1];
        prefixCount[0] = 1;

        int oddCount = 0;
        int ans = 0;
        for (int num : nums) {
            if (num % 2 == 1) {
                oddCount++;
            }

            // 只要历史前缀比当前少 k 个奇数，就能组成一个优美子数组。
            if (oddCount >= k) {
                ans += prefixCount[oddCount - k];
            }
            prefixCount[oddCount]++;
        }

        return ans;
    }
}

func numberOfSubarrays(nums []int, k int) int {
    prefixCount := make([]int, len(nums)+1)
    prefixCount[0] = 1

    oddCount := 0
    ans := 0
    for _, num := range nums {
        if num%2 == 1 {
            oddCount++
        }

        // 只要历史前缀比当前少 k 个奇数，就能组成一个优美子数组。
        if oddCount >= k {
            ans += prefixCount[oddCount-k]
        }
        prefixCount[oddCount]++
    }

    return ans
}

复杂度分析

时间复杂度：$O(n)$，n 为数组长度。凭什么：数组只被遍历一次，每个元素上做的是「一次奇偶判断、一次数组读、一次数组写」这些常数操作；因为计数用的是下标直接寻址的数组而非哈希表，连哈希计算和冲突处理的常数都省掉了。

空间复杂度：$O(n)$。凭什么：计数数组的长度是 n + 1，对应前缀奇数个数的全部可能取值；其余只有三个标量。若改用哈希表，空间同阶但常数更大——注意这里不能压成 $O(k)$，因为前缀值会一路涨到奇数总数。

关键点总结

看到「恰好等于某个值的子数组个数」，条件反射就是前缀和 + 计数哈希表：把「区间性质」翻译成「两个前缀之差」，再把「找配对」翻译成「查历史计数」。560、930、974、523 全是同一个模板，本题只是把「和」换成了「奇数个数」。

遇到只关心某种二元属性（奇偶、正负、是否等于某值）的题，先做 0/1 映射，把题目归约到已知题族。这一步转化说出来就是面试里的「我把它看成一个 0/1 数组的和为 K 问题」，比直接写代码更能体现建模能力。

先查询、后写入是前缀和计数的固定顺序，它保证配对的两个前缀位置严格不同。凡是 k 可能为 0 的题，这个顺序错了就会多算空区间。

空前缀必须预置一次（prefixCount[0] = 1），否则所有从数组开头起算的答案全部丢失。这是这类题里最高频的漏项。

当键的取值是有界的连续小整数时，用数组代替哈希表：读写更快、代码更短、没有装箱开销。判断依据是「键的范围是否与 n 同阶且非负」。

「恰好 k」还有另一条通路：「至多 k」减「至多 k-1」，用两次滑动窗口实现。它在「恰好 k 种不同元素」（992 题）这类无法用前缀差表达的题里是唯一解法，值得作为「还有别的思路吗」的备选答案说出来。

易错点总结

漏掉 prefixCount[0] = 1：nums = [1, 1, 2, 1, 1]、k = 3 时正确答案是 2，漏掉初始化后以下标 0 开头的那些子数组全被忽略，返回 0。

先写入计数再查询：nums = [2, 2]、k = 0 时每个位置都会把自己和自己配对，多算出 2 个长度为 0 的「子数组」，返回 5 而正确答案是 3。

缺少 oddCount >= k 的判断：nums = [2, 2, 2]、k = 1 时 oddCount - k = -1，Java 抛 ArrayIndexOutOfBoundsException、Go 直接 panic，程序在第一个元素上就崩了。

只在遇到奇数时才写入计数表：nums = [1, 2, 2, 1]、k = 2 的正确答案是 1，但偶数位置不计入后，prefixCount[0] 只有初始的 1，右端裹着偶数的那些子数组统统丢失，结果偏小。

只在遇到奇数时才更新答案：nums = [1, 1, 2, 2]、k = 2 的正确答案是 3（右端可以裹 0、1、2 个偶数），只在奇数位置累加会返回 1。

用 num % 2 == 1 判断奇数而数组含负数：本题保证元素为正所以安全，但同一段代码套到含负数的变体上时，-3 % 2 在 Java 和 Go 里都等于 -1，判断恒假，全部当成偶数，答案变 0。稳妥写法是 (num & 1) == 1。

计数数组开成长度 n 而不是 n + 1：nums 全为奇数时 oddCount 会取到 n，写入 prefixCount[n] 立刻越界。

误以为可以直接用滑动窗口求「恰好 k」：窗口内奇数个数达到 k 后，右侧还能继续吃进偶数、左侧也能吐出偶数，一个窗口对应多个子数组，单纯的「一个右端点配一个左端点」会漏算大量方案；要么记录左右两侧偶数段长度相乘，要么走「至多 k 减至多 k-1」，不能照搬求最值的滑窗模板。

把答案类型写成会溢出的量级估计错：n = 5 × 10^4 时子数组总数约 $1.25 \times 10^9$，虽然本题保证答案在 int 范围内，但若把 ans 的累加逻辑改成统计所有子数组就会溢出；改造这类题时要先估算答案上界。

把「优美」理解成「奇数个数不少于 k」：nums = [1, 1, 1]、k = 1 时按「至少」统计会得到 6，而「恰好」的正确答案是 3。读题时务必确认是「恰好」「至少」还是「至多」。

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	同一模板的原型，元素可正可负所以只能用哈希表而非有界数组计数
930. 和相同的二元子数组	中等	已经是 0/1 数组，省去映射一步，也可用「至多 k 减至多 k-1」的双滑窗对照
974. 和可被 K 整除的子数组	中等	计数的键换成前缀和的模，要处理负数取模修正为非负
523. 连续的子数组和	中等	同样按模分组，但只需判断存在性且要求长度至少为 2，存的是最早下标而非次数
525. 连续数组	中等	把 0 映射成 -1 后求和为 0 的最长子数组，存最早下标而不是出现次数
992. K 个不同整数的子数组	困难	「恰好 k」无法写成前缀差，必须用「至多 k 减至多 k-1」的双滑窗
1524. 和为奇数的子数组数目	中等	同样只关心奇偶，但只需统计前缀和奇偶两类的个数，计数表退化成两个变量
713. 乘积小于 K 的子数组	中等	「严格小于」有单调性，用滑动窗口按右端点累加窗口长度，不需要前缀计数