标签：#前缀和 #MySQL #哈希表 #LeetCode #面试

预计阅读时间：10分钟

开篇：产品经理的需求

产品经理："帮我查一下每个用户每天的累计消费金额。"

你写了个 SQL，数据量小的时候秒出。到了月底，100万条订单记录，查询跑了5分钟。

产品经理："能不能快点？"

问题出在子查询。每行都做一次 SUM，复杂度 O(n²)，数据量一上来就卡死。

前缀和就是来解决这个问题的——提前算好"累计值"，查询时做一次减法。

区间问题的终极解法：前缀和 + 哈希表

前缀和的基础用法是预处理区间求和。进阶玩法是配合哈希表做"子数组计数"。

如果 prefix[j] - prefix[i] = k，那么 nums[i..j-1] 就是一个和为 k 的子数组。转换成：找有多少对 (i, j) 满足 prefix[i] = prefix[j] - k。

遍历过程中用哈希表记录每个前缀和出现的次数，就能把问题从 O(n²) 降到 O(n)。

这种"把区间问题转换成两个累积值的差"的思路，和中国古代的"里"制很像——两点之间的距离不需要从头量，只需要看各自的里程桩，相减就是距离。前缀和数组就是原数组的"里程桩"。

MySQL 累积报表：为什么子查询这么慢

假设有一张订单表：

CREATETABLE orders (    order_id INT,    user_id INT,    order_date DATE,    amount DECIMAL(10,2));

数据（用户 123 的订单）：

order_id | user_id | order_date | amount---------|---------|------------|--------1        | 123     | 2024-01-01 | 100.002        | 123     | 2024-01-01 | 50.003        | 123     | 2024-01-02 | 200.004        | 123     | 2024-01-03 | 30.005        | 123     | 2024-01-03 | 70.006        | 123     | 2024-01-05 | 150.00

产品经理要查"每天累计消费"：

SELECT order_date, amount,       (SELECTSUM(amount) FROM orders o2 WHERE o2.order_date <= o1.order_date AND o2.user_id = o1.user_id) AS cumulativeFROM orders o1WHERE user_id =123;

执行过程拆解（为什么慢）

MySQL 执行这条 SQL 时，对外层每一行都执行一次子查询：

第1行：order_date=2024-01-01, amount=100  → 子查询：SUM(2024-01-01之前的amount) = 100  → 扫描了1行第2行：order_date=2024-01-01, amount=50  → 子查询：SUM(2024-01-01之前的amount) = 100 + 50 = 150  → 扫描了2行第3行：order_date=2024-01-02, amount=200  → 子查询：SUM(2024-01-02之前的amount) = 100 + 50 + 200 = 350  → 扫描了3行第4行：order_date=2024-01-03, amount=30  → 子查询：SUM(2024-01-03之前的amount) = 100 + 50 + 200 + 30 = 380  → 扫描了4行...以此类推

6 行数据，子查询总共扫描了 1+2+3+4+5+6 = 21 行。

如果用户有 1000 条订单，子查询总共扫描 1+2+3+...+1000 = 500,500 行。O(n²)。

100万条记录？子查询总共扫描约 5000亿 行。不卡才怪。

优化方案：SUM() OVER() 窗口函数

MySQL 8.0 引入了窗口函数，可以一行搞定：

SELECT user_id, order_date, amount,SUM(amount) OVER (PARTITIONBY user_id ORDERBY order_date) AS cumulativeFROM orders;

窗口函数的详细执行过程

SUM() OVER() 是怎么工作的？

数据按 (user_id, order_date) 排序：user_id | order_date | amount--------|------------|--------123     | 2024-01-01 | 100.00123     | 2024-01-01 | 50.00123     | 2024-01-02 | 200.00123     | 2024-01-03 | 30.00123     | 2024-01-03 | 70.00123     | 2024-01-05 | 150.00MySQL 扫描过程：第1行：user_id=123, date=2024-01-01, amount=100  → 累加器 = 100  → cumulative = 100第2行：user_id=123, date=2024-01-01, amount=50  → 累加器 = 100 + 50 = 150  → cumulative = 150第3行：user_id=123, date=2024-01-02, amount=200  → 累加器 = 150 + 200 = 350  → cumulative = 350第4行：user_id=123, date=2024-01-03, amount=30  → 累加器 = 350 + 30 = 380  → cumulative = 380第5行：user_id=123, date=2024-01-03, amount=70  → 累加器 = 380 + 70 = 450  → cumulative = 450第6行：user_id=123, date=2024-01-05, amount=150  → 累加器 = 450 + 150 = 600  → cumulative = 600

只扫描了 6 行，一次过。 O(n)。

MySQL 在内部维护了一个累加器变量，每读一行就加上当前 amount，然后输出当前累加值。这和我们在算法题里手动维护 prefixSum 变量是一模一样的思路。

预计算 + 差分查询

如果报表查询非常频繁，可以进一步预计算累积表：

-- 每天跑一次（比如凌晨）CREATETABLE user_daily_cumulative ASSELECT user_id, order_date,SUM(amount) AS daily_prefix_sumFROM ordersGROUPBY user_id, order_date;

然后查"第3天到第5天的总和"直接减法：

SELECT    (SELECT daily_prefix_sum FROM user_daily_cumulative WHERE user_id =123AND order_date ='2024-01-05')-    (SELECT daily_prefix_sum FROM user_daily_cumulative WHERE user_id =123AND order_date ='2024-01-02');

预处理 O(n)，每次查询 O(1)。报表场景中查询次数远多于更新次数，这个 trade-off 极其划算。

LeetCode 实战：和为 K 的子数组（LeetCode 560）

题目

给你一个整数数组 nums 和一个整数 k，统计和为 k 的连续子数组的个数。

比如 nums = [1, 1, 1], k = 2，有两个子数组：[1,1]（索引0-1）和 [1,1]（索引1-2）。

最笨的办法

枚举所有子数组的起点和终点，算和。O(n²)，超时。面试官会礼貌地让你回去等通知。

换个思路：把"子数组和"变成"两个前缀和的差"

nums[i..j] 的和等于 prefix[j+1] - prefix[i]。如果这个和等于 k，那就是 prefix[i] = prefix[j+1] - k。

什么意思呢？当我们遍历到位置 j，此时的前缀和是 prefix[j+1] 的时候，只需要知道之前有多少个前缀和等于 prefix[j+1] - k——那个数量就是有多少个子数组以 j 结尾且和为 k。

怎么快速知道"之前有多少个"？哈希表。

代码怎么写

publicint subarraySum(int[] nums, int k) {    Map<Integer, Integer> prefixCount = new HashMap<>();// 空前缀和为0，出现1次。这行非常关键！// 处理了子数组从索引0开始的情况    prefixCount.put(0, 1);int prefixSum = 0;int count = 0;for (int num : nums) {        prefixSum += num;         // 计算公式变形，prefixSum 是 prefix[j+1], need 是 prefix[i]int need = prefixSum - k;        count += prefixCount.getOrDefault(need, 0);        // 记录每个前缀和出现的次数        prefixCount.put(prefixSum,             prefixCount.getOrDefault(prefixSum, 0) + 1);    }return count;}

这里有几个坑

• prefixCount.put(0, 1) 必须在循环之前。考虑 nums = [1, 2, 3], k = 6，遍历到 3 时 prefixSum = 6，need = 0。如果哈希表里没有 0: 1，这种情况就会被漏掉——子数组 [1,2,3] 明明和为6，你却没找到。
• 先查 need，再 put 当前 prefixSum。顺序不能反，反了就会把自己也算进去。
• 这道题数组元素可以是负数，所以不能用滑动窗口。滑动窗口的前提是单调性，有负数就不单调了。
• 用 getOrDefault 而不是 get。不存在的前缀和返回 0，不是 null。

这道题和 MySQL 的联系

MySQL 用前缀和加速"区间求和"查询，本题用前缀和 + 哈希表解决"子数组计数"。都是把区间问题转换成两个前缀和的差。前缀和存储，差分查询。

总结

前缀和 + 哈希表 = 区间问题的终极解法。因为所有区间问题，本质上都是"两个累积值的差"。

觉得有收获？转发到技术群。

你写过带窗口函数的 SQL 吗？有没有被 cumulative sum 的需求折磨过？评论区聊聊。