🧠 通过提前累计数组的“历史和”，将任意连续区间的求和问题，转化为两次前缀值的相减。

一句话结论：
👉pre 数组要比原数组的长度多一
pre[0] = 0 是为了统一公式，避免边界特判
前缀和 + 哈希: 找历史区间

⭐ 模板

前缀和

  1. 初始化
    int n = nums.length;

    // 前缀和数组，多开一位
    int[] pre = new int[n + 1];
    pre[0] = 0;

    // [可选] 记录结果
    int res = 0;

  2. 循环处理（构建 / 使用前缀和）
    构建前缀和
    for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + nums[i];
    }

    使用前缀和（查询区间）
    // 区间 [l, r] 的和
    int sum = pre[r + 1] - pre[l];

二维前缀和

  1. 初始化
    int m = matrix.length;
    int n = matrix[ 0].length;

    // 二维前缀和数组，多开一行一列(多开一行一列是“哨兵设计”，用空间换逻辑统一，避免所有边界特判)
    int[][] pre = new int[m + 1][n + 1];

    // 第 0 行、第 0 列默认都是 0

  2. 循环处理（构建前缀和）
    for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
    pre[i + 1][j + 1] =
    pre[i][j + 1] // 上 + pre[i + 1][j] // 左 - pre[i][j] // 左上 + matrix[i][j]; // 自己
    }
    }

  3. 使用前缀和（查询区间）
    查询矩形 [r1, c1] ~ [r2, c2]（闭区间）
    int sum = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];

前缀和 + 哈希

  1. 初始化
    int n = nums.length;

    // 记录「前缀和(总距离) <-> 出现次数」
    Map<Integer, Integer> map = new HashMap<>();

    // 多开一位：表示“什么都不选”的前缀和
    map.put(0, 1);

    int target = 0; // 当前前缀和/余数
    int res = 0; // res 代表数组中「和等于 k 的子数组（连续区间）」的个数

  2. 循环处理（构建 / 使用前缀和）
    for (int i = 0; i < n; i++) {

    // 构建前缀和
    target += nums[i];

    // target - pre = k ,所以 target - k = pre ,pre 代表的是之前某个位置的前缀和

    if (map.containsKey(target - k)) {
    res += map.get(target - k);
    }

    // 更新当前前缀和出现次数
    map.put(target, map.getOrDefault(target, 0) + 1);
    }

  3. 返回结果
    return res;

Notice

  1. 哈希表存的是「次数」，不是下标（大多数题）

Map<Integer, Integer> map;
含义通常是：

key = 前缀和 (从起点（数组下标 0）出发，走到当前位置时，累计的总距离)
value = 这个前缀和出现过多少次

  1. 顺序非常重要（先算答案，再更新 map）

✅ 正确顺序

1
2
3
4
5
sum += nums[i];
if (map.containsKey(sum - k)) {
    res += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
  1. 区间元素

区间内不能重复用同一个位置的元素,不同区间之间可以重叠，所以元素位置可以被“重复使用”

  1. 二维前缀和

初始化多开一行一列
构建：上 + 左 − 左上 + 自己
查询：大 − 上 − 左 + 左上

  1. 什么场景用什么方法

一维前缀和:频繁地计算数组中任意一段连续子数组的和

二维前缀和:频繁地计算矩阵中任意矩形区域的和

前缀和+哈希:不关心具体的区间位置，只关心“ 有多少个”或“ 是否存在”满足条件的区间

相关练习题

1. LeetCode 303. 区域和检索 - 数组不可变

题意： 给定一个整数数组 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] )

2. LeetCode 560. 和为 K 的子数组

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

3. LeetCode 304. 二维区域和检索 - 矩阵不可变

题意： 给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和