算法优化：前缀和+哈希表

今天在leetcode上写到6952. 统计趣味子数组的数目这道题的时候出现了超时问题，由此学习了前缀和+哈希表的方法。

目前看到与此知识点相关的题目有如下：

1. 560.和为k的子数组 ，非常经典的前缀和+哈希表，可以从这一道题入手。
2. 6952. 统计趣味子数组的数目，这道题比上一到稍微难一点，但是不至于困难。

下面介绍一下 前缀和+哈希表

以560题为例，题目：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

解法：

首先，我们定义一个变量pre来表示当前位置之前的元素的和（0到 i 之和）。

我们使用哈希表来存储前缀和以及对应的出现次数。

在遍历过程中，如果哈希表中存在pre - k这个前缀和，说明存在一个子数组的和为k，这时我们将该前缀和出现的次数累加到结果res中。

然后，我们将当前的前缀和pre和对应的出现次数存储到哈希表中。如果哈希表中已经存在pre这个前缀和，说明存在多个子数组的和为pre，这时我们将其对应的出现次数加1；否则，我们初始化该前缀和的出现次数为1。

最后，遍历完整个数组后，返回结果res，即为总的子数组个数。

这个方法的时间复杂度是O(n)，其中n是数组的长度，因为需要遍历整个数组。空间复杂度是O(n)，因为需要使用哈希表来存储前缀和与对应的出现次数。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int pre = 0;
        int res = 0;
 
        Map<Integer,Integer> map = new HashMap();
        map.put(0,1);
 
        for(int i = 0;i < len;i++){
            pre += nums[i];
            if(map.containsKey(pre-k)){
                res += map.get(pre-k);
            }
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
 
        return res;
    }
}