3月13日报（前缀和）

约 1261 字大约 4 分钟

日报 leetcode

2026-03-13

补充不定滑窗的做法，直接填到昨天的日报了
做了一道 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;  
    }  
}

拆解分析代码：使用 getOrDefault ：如果 Map 中有这个 key 则返回对应的 value，如果 Map 里没有这个 key，不返回 null，而是返回你指定的那个 defaultValue

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

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

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分

思路解析

如果想让这个子数组的和尽量的大，那么当前的前缀和是固定不变的我们要减去历史上最小的前缀和由于由于子数组的元素和等于两个前缀和的差，所以求出 nums 的前缀和，问题就变成了： [[贪心#买卖股票最佳时机]] 本质是差不多的

一边遍历数组计算前缀和，一边维护最小前缀和，使用当前前缀和减去前缀和的最小值，就得到了以当前元素结尾的子数组和的最大值，然后以此来更新答案的最大值

请注意，由于题目要求子数组不能为空，应当先计算前缀和-最小前缀和，再更新最小前缀和。相当于不能在同一天买入股票又卖出股票

代码实现

class Solution {  
    public int maxSubArray(int[] nums) {  
        int ans = Integer.MIN_VALUE;  
        int minPreSum = 0;            // 记录最小前缀和
        int preSum = 0;               // 记录当前前缀和
        for (int x : nums) {  
            preSum += x;              // 获取前缀和
            ans = Math.max(ans, preSum - minPreSum);  // 减去前缀和最小值
            minPreSum = Math.min(minPreSum, preSum);  // 维护前缀和最小值
        }  
        return ans;  
    }  
}

给一个计算流程 [-2, 1, -3, 4, -1, 2, 1, -5, 4]

元素值	前缀和	最小前缀和	前缀和 - 最小前缀和
-2	-2	0	-2
1	-1	-2	1
-3	-4	-2	-2
4	0	-4	4
-1	-1	-4	3
2	1	-4	5
1	2	-4	6
-5	-3	-4	1
4	1	-4	5