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

骑猪看日落 2023-02-08 12:48 72阅读 0赞

再次分享一道前缀和的题目  
可以说，它在 [560. 和为 K 的子数组 前缀和的运用][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，统计子序列的个数，这个子序列有什么特征呢？

1.  连续的
2.  奇数个数为 k

它和之前的 [560. 和为 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<Integer, Integer> 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额外占用一个位置）

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

1.  HashMap 的 key 为 preSum，value 为 preSum 出现的次数
2.  数组的 index 为 preSum，value 为 preSum 的次数
3.  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;
        }
    }

我们看看效果

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]  
前缀和 + 哈希：40ms  
前缀和 + 数组：6ms

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

本篇完~

[560. _ K _]: https://blog.csdn.net/qq_42747210/article/details/122769910
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230208/16b6649e07f8499d865728c4a7212071.png