在算法面试中，数组区间求和是一个非常高频的操作。如果仅仅使用暴力循环，当查询次数非常多时，程序很容易超时。

今天我们来学习一种**“空间换时间”**的核心技巧——前缀和（Prefix Sum）。它能将区间查询的时间复杂度从 $O(N)$ 降维打击到 $O(1)$，是解决子数组问题的“瑞士军刀”。

LeetCode 303. 区域和检索 - 数组不可变（Easy）

题目链接：https://leetcode.cn/problems/range-sum-query-immutable/

标签：数组 | 前缀和 | 设计

所属模块：数组技巧

最后复习日期：2026-02-01

1. 题目描述

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

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right。

实现 NumArray 类：

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

2. 解题思路

直觉 (Intuition)

最直观的想法是，每次调用 sumRange(left, right) 时，写一个 for 循环从 left 加到 right。

问题：单次查询的时间复杂度是 $O(N)$。如果题目要求查询 $k$ 次（$k$ 可能高达 $10^4$），总时间复杂度就是 $O(k \cdot N)$。这在数据量大时会直接导致 Time Limit Exceeded (TLE)。

核心技巧 (Core Technique)

我们需要一种方法，能够快速（最好是 $O(1)$）得到任意区间的和。

前缀和数组应运而生：我们预先计算出从数组起点到每个位置的累加和，存入一个新数组 preSum。

定义 preSum[i] 为 nums[0...i-1] 的和。
优势：一旦 preSum 构造完成，任意区间的和都可以通过两次查表相减得到，无需遍历。

可视化推导 (Visualization)

假设我们需要计算 nums[left...right] 的和：

preSum[right+1] 代表 nums[0...right] 的总和。
preSum[left] 代表 nums[0...left-1] 的总和。
两者相减：
$$\text{sumRange}(left, right) = \text{preSum}[right+1] - \text{preSum}[left]$$

通过减法，我们“切掉”了 left 左边的部分，只保留了 [left, right] 区间的和。

3. 代码实现

class NumArray {
    // preSum[i] 存储 nums[0...i-1] 的累加和
    // 这种定义方式是为了方便处理 left=0 的情况，无需特殊判断
    private int[] preSum;

    public NumArray(int[] nums) {
        // 核心技巧：preSum 长度要比 nums 多 1
        // preSum[0] 默认为 0，代表空数组的和
        preSum = new int[nums.length + 1];
        
        // 构造前缀和数组
        for (int i = 0; i < nums.length; i++) {
            // 当前前缀和 = 上一个前缀和 + 当前元素
            // 这里的 nums[i] 对应 preSum[i+1]
            preSum[i + 1] = preSum[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        // 利用推导公式直接 O(1) 返回
        // 查询闭区间 [left, right]，对应 preSum 下标是 [left, right+1]
        return preSum[right + 1] - preSum[left];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */

没问题！把你的暴力解法作为“思路演进”的第一步放进去，这样文章的逻辑更完整，能体现出**“从 $O(N^2)$ 到 $O(N)$”**的优化过程，这是面试官最喜欢看到的思考路径。

我已经把你刚才写的代码整合进去了，放在**“方法一：暴力前缀和”**板块。

您可以直接复制下面的完整内容，保存为 source/_posts/subarray-sum-equals-k.md。

LeetCode 560. 和为 K 的子数组（Medium）

题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/

标签：数组 | 哈希表 | 前缀和

所属模块：数组与哈希表

最后复习日期：2026-02-01

1. 题目描述

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

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
解释：[1,1] 与 [1,1] 为两个符合条件的子数组。

2. 方法一：暴力前缀和（我的初探）

思路分析

最直观的想法是：既然要计算子数组的和，那我就先把前缀和数组 preSum 算出来。
有了 preSum 之后，任意子数组 nums[j...i-1] 的和就可以通过 preSum[i] - preSum[j] 在 $O(1)$ 时间算出。
然后，我使用双层循环枚举所有的起点和终点，判断差值是否等于 k。

我的代码实现

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 1. 构造前缀和数组 (长度 N+1)
        int[] preSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        
        int res = 0;
        
        // 2. 双层循环枚举所有子数组
        // i 代表右边界 (对应的 preSum 索引)
        // j 代表左边界 (对应的 preSum 索引)
        for (int i = 1; i < preSum.length; i++) {
            for (int j = 0; j < i; j++) {
                // 判断子数组和是否为 k
                if (preSum[i] - preSum[j] == k) {
                    res++;
                }
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度：$O(N^2)$。
- 虽然利用前缀和省去了计算子数组和的时间，但双层循环依然跑不掉。
- 当 $N=20000$ 时，计算量达到 $4 \times 10^8$，在 LeetCode 上会提示 TLE (超时)，但这逻辑本身是完全正确的。
空间复杂度：$O(N)$，用于存储 preSum 数组。

3. 方法二：前缀和 + 哈希表（进阶优化）

优化思路

暴力法慢在**“每次都要回头找”**。

当我们遍历到 i 时，我们想知道：在 i 之前，有多少个 j 满足 preSum[i] - preSum[j] == k？

移项可得：

$$preSum[j] == preSum[i] - k$$

与其回头傻傻遍历，不如一边遍历，一边用哈希表记录下来之前出现过的 preSum 及其出现次数。这样查找 preSum[j] 的时间就变成了 $O(1)$。

优化代码实现

Java

class Solution {
    public int subarraySum(int[] nums, int k) {
        // Key: 前缀和的值, Value: 该前缀和出现的次数
        Map<Integer, Integer> preSumMap = new HashMap<>();
        
        // Base Case: 前缀和为 0 出现 1 次
        // 处理从数组开头就是目标子数组的情况 (preSum - k = 0)
        preSumMap.put(0, 1);
        
        int preSum = 0;
        int count = 0;
        
        for (int num : nums) {
            preSum += num;
            
            // 核心查询：之前是否出现过 (preSum - k)
            if (preSumMap.containsKey(preSum - k)) {
                count += preSumMap.get(preSum - k);
            }
            
            // 将当前前缀和记录到 Map 中
            preSumMap.put(preSum, preSumMap.getOrDefault(preSum, 0) + 1);
        }
        
        return count;
    }
}

复杂度分析

时间复杂度：$O(N)$。只需要遍历一次数组。
空间复杂度：$O(N)$。哈希表存储前缀和。

4. 易错点 & 调试经验

Map 初始化：
- 优化解法中，千万别忘了 preSumMap.put(0, 1)。如果不加这行，所有从下标 0 开始的符合条件的子数组都会被漏掉。
暴力法的边界：
- 在我最初写暴力法时，内层循环写成了 j < preSum.length，导致重复计算和逻辑错误。正确的应该是 j < i，因为左边界一定在右边界左侧。

5. 相关变式

LC 1. 两数之和：本题其实是“两数之和”的前缀和版。
LC 974. 和可被 K 整除的子数组：把 Key 换成 preSum % K 即可。

这是按照你要求的格式（LeetCode 5 的笔记风格）整理的 LeetCode 1109 题解。你可以直接复制保存为 source/_posts/corporate-flight-bookings.md。

LeetCode 1109. 航班预订统计（Medium）

题目链接：https://leetcode.cn/problems/corporate-flight-bookings/

标签：数组 | 差分数组 | 前缀和

所属模块：数组技巧

最后复习日期：2026-02-02

复习次数：1

掌握程度：🌟

1. 题目描述

这里有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [first, last, seats] 意味着在从 first 到 last （包含 first 和 last ）的 每个航班 上预订了 seats 个座位。

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25

2. 核心框架 / 套路归纳

这题的最优解是 差分数组 (Difference Array)。

适用场景：
如果题目要求对数组进行频繁的区间修改（例如：在区间 [i, j] 加上 val），而最后只需要一次查询结果。

核心公式：

定义：diff[i] = nums[i] - nums[i-1]。
区间修改：想让 nums[i...j] 增加 val，只需要：
- diff[i] += val
- diff[j+1] -= val
还原：nums[i] = nums[i-1] + diff[i]（实际上就是对差分数组求前缀和）。

为什么用这个框架？
暴力循环修改的时间复杂度是 $O(N)$，如果有 $k$ 次修改，总复杂度是 $O(k \cdot N)$，容易超时。而差分数组将区间修改的时间复杂度降低到了 $O(1)$。

3. 思路分析

暴力思路

初始化一个长度为 n 的数组。遍历每一条预订记录 [first, last, seats]，用一个 for 循环把数组中从 first 到 last 的所有元素都加上 seats。

时间复杂度：$O(N \times \text{bookings.length})$。
结果：当数据量较大时，Time Limit Exceeded (TLE)。

优化思路（差分数组）

我们可以把问题想象成“公交车上下客”：

对于一条记录 [first, last, seats]，相当于在 first 这一站，车上多了 seats 个人。
这些人在车上一直坐到 last 站。
注意！他们是在 last 的下一站（即 last + 1）才下车的。

所以我们只需要操作 diff 数组：

diff[first] += seats
diff[last + 1] -= seats

最后，把每一站的变化量累加起来（前缀和），就是每一站当前的实际人数。

4. 代码实现

Java 实现

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        // 1. 定义差分数组
        // 长度设为 n 即可，虽然 diff[j+1] 可能越界，但我们在循环里判断
        int[] diff = new int[n];

        // 2. 遍历每一条预订记录，进行 O(1) 的区间更新
        for (int[] booking : bookings) {
            // 题目给的是 1-based index (1~n)，我们需要转成 0-based (0~n-1)
            int i = booking[0] - 1; // 起始索引
            int j = booking[1] - 1; // 结束索引
            int val = booking[2];   // 增加的座位数

            // 核心操作 1: 区间起点 + val
            diff[i] += val;

            // 核心操作 2: 区间终点的下一位 - val
            // 注意越界检查：只有当 j 不是最后一个元素时，才需要减
            // 如果 j 是数组末尾，说明这就加到最后了，后面没有元素需要抵消增量
            if (j + 1 < n) {
                diff[j + 1] -= val;
            }
        }

        // 3. 还原数组（原地修改 diff 即可节省空间）
        // diff[i] 变成了前缀和，即为原数组的值
        for (int i = 1; i < n; i++) {
            diff[i] = diff[i - 1] + diff[i];
        }

        return diff;
    }
}

5. 复杂度分析

时间复杂度：$O(N + K)$
- $N$ 是数组长度（航班数），$K$ 是 bookings 的数量。
- 我们需要遍历一次 bookings 进行差分更新 ($O(K)$)，然后遍历一次 diff 数组进行还原 ($O(N)$)。
空间复杂度：$O(N)$
- 需要一个长度为 $N$ 的数组来存储结果（如果复用 diff 数组作为结果返回，可视为 $O(1)$ 的额外空间）。

6. 易错点 & 调试经验

索引转换：
- 题目通常给的是从 1 开始的索引（1-based），而代码中数组是从 0 开始的。一定要记得 index - 1。
区间右边界：
- 差分数组的减操作是在 j + 1 也就是“终点的后一位”。
- 错误写法：diff[j] -= val （这样会导致终点那一位也没加上值）。
- 正确写法：diff[j + 1] -= val。
数组越界：
- 当 j 是数组最后一个位置时，j + 1 会越界。这时候不需要执行减操作，因为这意味着增量一直持续到数组结束。

7. 相关变式 & 高频延伸题目

相似题：
- LC 1094. 拼车 (Medium)：本质完全一样，只是把“航班”换成了“车位”，把“预订”换成了“上下车”，最后判断任何时刻是否超载。
- LC 370. 区间加法 (Medium)：差分数组的裸题（需要会员）。
进阶版：
- 二维差分数组（处理矩阵区域修改问题）。