1248.统计「优美子数组」前缀和的运用

再次分享一道前缀和的题目
可以说它在 560、和为 K 的子数组 前缀和的运用 上面套了壳
本质都是计算前缀和数组，然后用 Map 优化访问效率。

链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays

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

题目分析

这道题，给定nums，统计子序列的个数，这个子序列有什么特征呢？

连续的奇数个数为 k

它和之前的 560、和为 K 的子数组 前缀和的运用 ，有什么关联呢？
其实，把 nums 对 2 求余，转为 0 和 1 的子序列。那么寻找奇数个数为 k 的子数组，等价于寻找和为 k 的子数组。过程如下：

nums = [1,1,2,1,1], k = 3

odd = [1,1,0,1,1],

把 odd 看成差分数组，对它求前缀和，便于下一步统计 和为k 的子数组个数。

前缀和数组 preSum = [1,2,2,3,4]

定义 result = 0，看看前缀和数组，值为 preSum[i] - k 的元素，有几个？

遍历到1，1- 3 = -2， preSum 数组不存在 -2；
遍历到2，2 - 3 = -1， preSum 数组不存在 -1；
遍历到2，2 - 3 = -1， preSum 数组不存在 -1；
遍历到3，3 - 3 = 0， preSum 数组存在 0，result 加 1，等于1
遍历到4，4 - 3 = 0， preSum 数组存在 0，result 加 1，等于2

最终，和为k的子数组个数是2，因此原数组中，优美子数组的个数为 2

代码

class Solution { public int numberOfSubarrays(int[] nums, int k) { int size = nums.length; int res = 0; int preSum = 0; // 1 定义map，保存和的出现次数 HashMap map = new HashMap<>(); // 很有必要的初始化，若preSum刚好等于k时， // preSum - k = 0，和为k的子序列个数加一 map.put(0,1); for (int num: nums) { // 转为 0 1 序列 int odd = num & 1; // 2.1 计算前缀和 preSum += odd; if (map.containsKey(preSum - k)) { // 3 前缀和为k的子序列的个数 ，累加 res += map.get(preSum - k); } // 2.2 前缀和为preSum的出现次数 map.put(preSum, map.getOrDefault(preSum, 0) + 1); } return res; }}

时间复杂度：O(n)
空间复杂度：O(n)

到此为止，还能不能优化？

算法上没啥优化，但是存储方面可以优化。HashMap 的负载因子是 0.75 （避免哈希冲突），因此它占用的空间一般比实际元素所需的多。假设给定的 nums 有15个元素，它就会保存15个元素，实际空间可能是 15 / 0.75 = 20 个。

吹毛求疵一下，我们不用map，改用数组，刚好存 lenght + 1 个，不多不少。

能够这样做的前提是：
preSum 的结果是可穷尽的，针对本题，假如 nums 数组元素没有重复，preSum 的个数最多是 length + 1 （0额外占用一个位置）

思路如果转不过来，可以这样想：

HashMap 的 key 为 preSum，value 为 preSum 出现的次数数组的 index 为 preSum，value 为 preSum 的次数HashMap 和 数组的访问某元素的复杂度都是 O(1)。或者这么说，HashMap 底层就是用数组实现的。

因此：用数组来代替 HashMap 是完全没问题的

class Solution { public int numberOfSubarrays(int[] nums, int k) { int size = nums.length; int res = 0; int preSum = 0; // 1 定义map，保存和的出现次数 。 int[] map = new int[size+1]; // 数组，而不是 hashMap // 很有必要的初始化，若preSum刚好等于k时， // preSum - k = 0，和为k的子序列个数加一 map[0]=1; for (int num: nums) { // 转为 0 1 序列 int odd = num & 1; // 2.1 计算前缀和 preSum += odd; if (preSum - k >= 0) { // 3 前缀和为k的子序列的个数 ，累加 res += map[preSum - k]; } // 2.2 前缀和为preSum的出现次数 map[preSum] = map[preSum] > 0 ? map[preSum] + 1 : 1; } return res; }}

我们看看效果

前缀和 + 哈希：40ms
前缀和 + 数组：6ms

知识就是力量，科学技术是第一生产力

本篇完~