• 补充不定滑窗的做法，直接填到昨天的日报了
• 做了一道 ez 一道 mid 有点头大了，感觉还是没有理解透彻，明天再继续看

前缀和

在完成 hot100 中 和为K的子数组 这道题目前，我们先去学习 区域和检索 -数组不可变 来练习前缀和的使用

区域和检索 -数组不可变

题目要求： 给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right 实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

思路解析

前缀和的核心公式： 设 $P[i]$ 是数组前 $i$ 个元素的和

$$P[i] = nums[0] + nums[1] + \dots + nums[i-1]$$

那么 left 到right的区间和就是：

$$Sum(left, right) = P[right + 1] - P[left]$$

如何理解呢 为什么预处理数组长度要 $n + 1$？ 假设我们定义 preSum 长度为 n + 1 并让 preSum[0] = 0 那么 preSum[1] 就是前一个数的和，而 preSum[i] 就是前 i 个数的和 以此，好处：当你计算从索引 0 开始的区间时（例如 sumRange(0, 2)），公式变为 preSum[3] - preSum[0]。因为 preSum[0] 是 0，你就不需要写额外的 if 语句去处理 left == 0 的边界情况了

代码实现

class NumArray {  
    private final int[] s;  // 储存前缀和
    public NumArray(int[] nums) {  
        s = new int[nums.length + 1];  
        for (int i = 0; i < nums.length; i++) {  
            s[i + 1] = s[i] + nums[i];  //  i + 1 是为了方便计算和对齐
        }  
    }  
  
    public int sumRange(int left, int right) {  
        return s[right + 1] - s[left];  
    }  
}  
  
/**  
 * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */

和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列

思路解析

我们使用前缀和和哈希表来解答这个问题 先预处理前缀和，之后使用哈希表来检查和记录，具体实现看代码

代码实现

class Solution {  
    public int subarraySum(int[] nums, int k) {  
        int n = nums.length;  // 处理前缀和
        int[] s = new int[n + 1];  
        for (int i = 0; i < n; i++) {  
            s[i + 1] = s[i] + nums[i];  
        }  
  
        Map<Integer, Integer> cnt = new HashMap<>(n +1, 1);  // 预分配空间
        int ans = 0;  
        for (int sj : s) {  
            ans += cnt.getOrDefault(sj - k, 0);   // 查找以及记录
            cnt.merge(sj, 1, Integer::sum);       // cnt[sj]++
        }  
        return ans;  
    }  
}

拆解分析代码： ans += cnt.getOrDefault(sj - k, 0); 首先进行查询，查询在此之前有没有记录过 sj-k 的出现。如果有，而且出现了 $N$ 次，那就说明以当前点结尾，有 $N$ 个子数组的和正好等于 $k$。于是你的答案 ans 就加上 $N$

cnt.merge(sj, 1, Integer::sum); 将新的数据跟老数据进行合并