前缀和（Prefix Sum / Cumulative Sum）专题精讲：从核心公式到 29 道 LeetCode 源码实战

前缀和（Prefix Sum / Cumulative Sum）专题精讲：从核心公式到 29 道 LeetCode 源码实战

【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo

导读

前缀和（Cumulative Sum，又称 Prefix Sum）是算法面试中最基础也最高频的数组技巧之一：预处理一遍数组，就能把任意子数组的区间求和从 O(n) 降到 O(1)。本文以 Interview_DS_Algo 仓库中 Arrays/Cumulative_Sum(Prefix Array)/README.md/README.md) 为骨架，完整梳理该专题收录的 29 道 LeetCode 经典题目，并结合仓库内 C++ 源码逐类拆解一维前缀和、前缀和 + 哈希表、前缀和 + 二分、二维前缀和等核心套路，让你读完即可对"子数组求和 / 计数 / 最值"类问题形成系统打法。

前缀和（Cumulative Sum）数组概念示意图/Cumulative Sum Array.jpg)

一、前缀和是什么：一个公式吃透"区间求和"

前缀和的核心思想是空间换时间：预先计算pre[i] = nums[0] + nums[1] + ... + nums[i]，之后任意子数组nums[l..r]的和都能用一次减法得到：

sum(l, r) = pre[r] - pre[l-1] （约定 pre[-1] = 0）

对应的 O(1) 空间滚动写法是：先求总数组和totalSum，从左到右维护leftSum，那么rightSum = totalSum - leftSum，全程只需两个变量。

仓库中的 Find Pivot Index.cpp/Find Pivot Index.cpp)（Leetcode-724，源码标注考察公司：Amazon、Adobe、Coupang）是理解这一公式的最佳入门题，它同时给出了两种典型实现：

Approach-1（O(n) 空间）：先构建累计和数组cumu_sum[]，再逐位判断"左侧和 == 右侧和"：

long long cumu_sum[n]; cumu_sum[0] = a[0]; long long totalSum = a[0]; for(int i = 1; i<n; i++) { totalSum += a[i]; cumu_sum[i] = cumu_sum[i-1] + a[i]; } // 对位置 i： // left_sum = cumu_sum[i] - a[i] // right_sum = totalSum - left_sum - a[i]

源码注释中用示例A[] = {1, 3, 5, 2, 2}推导：cumu_sum = {1, 4, 9, 11, 13}，TotalSum = 13，当i = 1时left_sum = 4 - 3 = 1，right_sum = 13 - 1 - 3 = 9，左右不相等，继续扫描。这种把"前缀和数组 + 全局总和"结合求两侧和的写法，是整个专题最通用的分析框架。

Approach-2（O(1) 空间）：边扫描边累加left_sum，右侧和随时用totalSum - left_sum - a[i]算出，省掉整个前缀数组。

一句话记忆：任何"两侧和 / 子数组和"比较问题，都可以先预处理前缀，再 O(1) 取区间和。

二、最常用的三种前缀和套路

套路 1：一维前缀和 —— 区间求和 / 区间统计

典型代表是 Count Vowel Strings in Ranges.cpp/Count Vowel Strings in Ranges.cpp)（Leetcode-2559），它把"某个下标区间内有多少个满足条件的元素"的统计问题化为一维前缀和：

vector<int> cumSum(N); int sum = 0; for(int i = 0; i < N; i++) { // O(N) 预处理 if(isVowel(words[i][0]) && isVowel(words[i].back())) { sum++; } cumSum[i] = sum; // 前缀计数 } for(int i = 0; i < Q; i++) { // O(Q) 回答每个查询 int l = queries[i][0]; int r = queries[i][1]; result[i] = cumSum[r] - ((l > 0) ? cumSum[l-1] : 0); // 区间计数 = pre[r] - pre[l-1] }

总复杂度 O(N + Q)，一次预处理、每次查询 O(1)。注意l = 0时要特判cumSum[l-1]越界，这是前缀和区间查询的经典边界细节。

同套路的题目还有 Minimum Average Difference.cpp/Minimum Average Difference.cpp)（Leetcode-2256，源码标注考察公司：Amazon、Paytm）：一边累加LS一边让RS = sum - LS，左侧平均为LS/(i+1)，右侧平均为(i == n-1) ? 0 : RS/(n-i-1)，取绝对差最小的下标，整体 O(n) 时间、O(1) 空间。

套路 2：前缀和 + 哈希表 —— 子数组"和 / 余数"等式计数

当题目要求统计满足某种和等式条件的子数组个数或最长长度时，光靠前缀和数组不够，需要用unordered_map记录"某个前缀和值最早 / 最近出现的位置"。

经典题 Continuous Subarray Sum.cpp/Continuous Subarray Sum.cpp)（Leetcode-523，源码标注考察公司：Amazon、Facebook、Paytm）：

unordered_map<int, int> mp; mp[0] = -1; // 空前缀余数为 0，位置记为 -1 int sum = 0; for(int i = 0; i<n; i++) { sum += nums[i]; int remainder = sum % k; if(mp.find(remainder) != mp.end()) { if(i - mp[remainder] >= 2) // 子数组长度至少为 2 return true; } else { mp[remainder] = i; // 只记录余数首次出现的位置 } }

其数学依据是：(pre[j] - pre[i]) % k == 0等价于pre[j] % k == pre[i] % k，所以只要前缀余数重复出现，中间那段子数组的和必然能被 k 整除。用余数而不是原值作为哈希键，是该套路与普通"和为 K 的子数组"（Leetcode-560）的关键区别。

同套路题包括：

• Make Sum Divisible by P.cpp/Make Sum Divisible by P.cpp)（Leetcode-1590）：先SUM = (SUM + num) % p求出整体余数target，再在遍历中找remain = (curr - target + p) % p的最短移除长度，(curr - target + p) % p是为了保证余数为非负；
• Contiguous Array.cpp/Contiguous Array.cpp)（Leetcode-525，源码标注考察公司：Meta、Google）：把 0 视为 -1、1 视为 +1，问题转化为"前缀和相同的最长区间"，mp[0] = -1初始化 +maxL = max(maxL, i - mp[currSum])即为答案，源码注释明确说明它与 Leetcode-560/930/1074 同属一个模式；
• Minimum Operations to Reduce X to Zero.cpp/Minimum Operations to Reduce X to Zero.cpp)（Leetcode-1658，源码标注考察公司：Amazon）：把"两端删元素凑 X"转化为"找中间最长的和为sum - x的子数组"，用mp[sum - restSum]前缀哈希 O(n) 求解；源码还附带一个 O(2^n) 递归版本（Approach-2）作对比，并指出即使记忆化仍会超时，借此说明前缀和哈希方案的必要性；
• Number of Sub-arrays With Odd Sum.cpp/Number of Sub-arrays With Odd Sum.cpp)（Leetcode-1524）、Count of Interesting Subarrays.cpp/Count of Interesting Subarrays.cpp)（Leetcode-2845）、Maximum Absolute Sum of Any Subarray.cpp/Maximum Absolute Sum of Any Subarray.cpp)（Leetcode-1749）等均沿用"前缀 + 哈希计数"的思路。

套路 3：前缀和 + 差分思想 —— 区间批量更新

Range Addition.cpp/Range Addition.cpp)（Leetcode-370，源码标注考察公司：Google，文件内自带完整题目描述与逐步演算示例）展示了前缀和的"逆操作"——差分数组：区间[start, end]统一加inc，不必逐点更新，只需在nums[start] += inc、nums[end+1] -= inc，最后做一次前缀累加即可还原：

// Approach-2 (Using concept of Cumulative Sum) : Time : O(Q+n) nums[start] += update; if(end_next < length) nums[end_next] -= update; // 最后做一次前缀累加 for(int i = 1; i<length; i++) nums[i] += nums[i-1];

源码同时给出 Brute Force（O(Q·n)）作为对照：对每次更新从start到end逐元素累加。差分写法把复杂度降到 O(Q + n)，核心注释点明了原理："只在 start 打 + 号，因为前缀累加会自然向后传播；为了不让 end 之后的元素被波及，在 end+1 处打 - 号抵消。"

三、前缀和的进阶应用：二维、二分与前缀最值

前缀和不止能解决一维线性问题，在仓库源码中还能看到它与其他技巧的组合：

1. 二维前缀和（2-D Prefix Sum）：Maximum Side Length of a Square with Sum Less than or Equal to Threshold.cpp/Maximum Side Length of a Square with Sum Less than or Equal to Threshold.cpp)（Leetcode-1292）需要在矩阵中快速求正方形区域和；Equal Sum Grid Partition I.cpp/Equal Sum Grid Partition I.cpp)（Leetcode-3546）与 Equal Sum Grid Partition II.cpp/Equal Sum Grid Partition II.cpp)（Leetcode-3548）则要求把网格切成和相等的区域。这类题把一维的pre[r] - pre[l-1]扩展为二维容斥公式sum(x1,y1,x2,y2) = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]。

2. 前缀和 + 二分查找：Longest Subsequence With Limited Sum.cpp/Longest Subsequence With Limited Sum.cpp)（Leetcode-2389）先排序再构建前缀和，对每个查询用upper_bound找到前缀和不超过限额的最大长度，单次查询 O(log n)。

3. 前缀和的"游戏策略"应用：Grid Game.cpp/Grid Game.cpp)（Leetcode-2017）用两个"剩余和"模拟两个机器人的博弈：第一行剩余和firstRowRemainSum从总和逐步减去，第二行累计和secondRowRemainSum逐步加上，机器人 2 的最佳得分是两者较大值，机器人 1 要使该值最小，整体 O(col) 时间、O(1) 空间：

for(int Robot1Col = 0; Robot1Col < grid[0].size(); Robot1Col++) { firstRowRemainSum -= grid[0][Robot1Col]; long long bestOfRobot2 = max(firstRowRemainSum, secondRowRemainSum); minimizedRobot2Sum = min(minimizedRobot2Sum, bestOfRobot2); secondRowRemainSum += grid[1][Robot1Col]; }

4. 前缀和 + 滑动窗口 / 前缀最值：K Radius Subarray Averages.cpp/K Radius Subarray Averages.cpp)（Leetcode-2090，源码标注考察公司：Amazon）用前缀和在 O(n) 内求所有长度2k+1的窗口平均值，并特判k == 0与n < 2*k+1的边界情况，源码注释还指出仓库中另有 滑动窗口解法；Maximum Sum of Two Non-Overlapping Subarrays.cpp/Maximum Sum of Two Non-Overlapping Subarrays.cpp)（Leetcode-1031）、Maximum Frequency of an Element After Performing Operations I.cpp/Maximum Frequency of an Element After Performing Operations I.cpp)（Leetcode-3346）、Sum of Distances.cpp/Sum of Distances.cpp)（Leetcode-2615）、Jump Game IX.cpp/Jump Game IX.cpp)（Leetcode-3660）、Count Subarrays With Majority Element I & II.cpp/Count Subarrays With Majority Element I & II.cpp)（Leetcode-3737/3739）、Concatenate Non-Zero Digits and Multiply by Sum II.cpp/Concatenate Non-Zero Digits and Multiply by Sum II.cpp)（Leetcode-3756）等题目也都在前缀和的基础上叠加了哈希、单调栈或贪心策略。

四、专题完整题单（继承自 README）

下表完整收录 Arrays/Cumulative_Sum(Prefix Array)/README.md/README.md) 中列出的全部题目，点击可直达仓库内的 C++ 源码：

Problem Name	源码
Range Addition（Leetcode-370）	Range Addition.cpp/Range Addition.cpp)
Range Addition II（Leetcode-598）	Range Addition II.cpp/Range Addition II.cpp)
Find Pivot Index（Leetcode-724）	Find Pivot Index.cpp/Find Pivot Index.cpp)
Continuous Subarray Sum（Leetcode-523）	Continuous Subarray Sum.cpp/Continuous Subarray Sum.cpp)
Minimum Average Difference（Leetcode-2256）	Minimum Average Difference.cpp/Minimum Average Difference.cpp)
Longest Subsequence With Limited Sum（Leetcode-2389）	Longest Subsequence With Limited Sum.cpp/Longest Subsequence With Limited Sum.cpp)
K Radius Subarray Averages（Leetcode-2090）	K Radius Subarray Averages.cpp/K Radius Subarray Averages.cpp)
Minimum Penalty for a Shop（Leetcode-2483）	Minimum Penalty for a Shop.cpp/Minimum Penalty for a Shop.cpp)
Minimum Operations to Reduce X to Zero（Leetcode-1658）	Minimum Operations to Reduce X to Zero.cpp/Minimum Operations to Reduce X to Zero.cpp)
Minimum Amount of Time to Collect Garbage（Leetcode-2391）	Minimum Amount of Time to Collect Garbage.cpp/Minimum Amount of Time to Collect Garbage.cpp)
Contiguous Array（Leetcode-525）	Contiguous Array.cpp/Contiguous Array.cpp)
Count Number of Nice Subarrays（Leetcode-1248）	Count Number of Nice Subarrays.cpp/Count Number of Nice Subarrays.cpp)
Make Sum Divisible by P（Leetcode-1590）	Make Sum Divisible by P.cpp/Make Sum Divisible by P.cpp)
Max Chunks To Make Sorted（Leetcode-769）	Max Chunks To Make Sorted.cpp/Max Chunks To Make Sorted.cpp)
Count Vowel Strings in Ranges（Leetcode-2559）	Count Vowel Strings in Ranges.cpp/Count Vowel Strings in Ranges.cpp)
Number of Ways to Split Array（Leetcode-2270）	Number of Ways to Split Array.cpp/Number of Ways to Split Array.cpp)
Grid Game（Leetcode-2017）	Grid Game.cpp/Grid Game.cpp)
Number of Sub-arrays With Odd Sum（Leetcode-1524）	Number of Sub-arrays With Odd Sum.cpp/Number of Sub-arrays With Odd Sum.cpp)
Maximum Absolute Sum of Any Subarray（Leetcode-1749）	Maximum Absolute Sum of Any Subarray.cpp/Maximum Absolute Sum of Any Subarray.cpp)
Count of Interesting Subarrays（Leetcode-2845）	Count of Interesting Subarrays.cpp/Count of Interesting Subarrays.cpp)
Maximum Frequency of an Element After Performing Operations I（Leetcode-3346）	Maximum Frequency of an Element After Performing Operations I.cpp/Maximum Frequency of an Element After Performing Operations I.cpp)
Maximum Side Length of a Square with Sum Less than or Equal to Threshold（Leetcode-1292）	Maximum Side Length of a Square with Sum Less than or Equal to Threshold.cpp/Maximum Side Length of a Square with Sum Less than or Equal to Threshold.cpp)
Equal Sum Grid Partition I（Leetcode-3546）	Equal Sum Grid Partition I.cpp/Equal Sum Grid Partition I.cpp)
Equal Sum Grid Partition II（Leetcode-3548）	Equal Sum Grid Partition II.cpp/Equal Sum Grid Partition II.cpp)
Sum of Distances（Leetcode-2615）	Sum of Distances.cpp/Sum of Distances.cpp)
Jump Game IX（Leetcode-3660）	Jump Game IX.cpp/Jump Game IX.cpp)
Count Subarrays With Majority Element I & II（Leetcode-3737 & 3739）	Count Subarrays With Majority Element I & II.cpp/Count Subarrays With Majority Element I & II.cpp)
Concatenate Non-Zero Digits and Multiply by Sum II（Leetcode-3756）	Concatenate Non-Zero Digits and Multiply by Sum II.cpp/Concatenate Non-Zero Digits and Multiply by Sum II.cpp)
Maximum Sum of Two Non-Overlapping Subarrays（Leetcode-1031）	Maximum Sum of Two Non-Overlapping Subarrays.cpp/Maximum Sum of Two Non-Overlapping Subarrays.cpp)

五、题单复杂度速查与刷题路线

从仓库源码中可以汇总出该专题的典型复杂度分布：

套路	代表题	时间复杂度	空间复杂度
一维前缀和 + 遍历	Find Pivot Index、Number of Ways to Split Array、Minimum Average Difference	O(n)	O(1)~O(n)
一维前缀和 + 区间查询	Count Vowel Strings in Ranges	O(n + q)	O(n)
前缀和 + 哈希表	Continuous Subarray Sum、Contiguous Array、Make Sum Divisible by P、Minimum Operations to Reduce X to Zero	O(n)	O(n)
差分数组（前缀和逆操作）	Range Addition	O(q + n)	O(n)
前缀和 + 二分	Longest Subsequence With Limited Sum	O(n log n + q log n)	O(n)
前缀和 + 窗口 / 前缀最值	K Radius Subarray Averages、Maximum Sum of Two Non-Overlapping Subarrays	O(n)	O(n)
二维前缀和	Maximum Side Length of a Square、Equal Sum Grid Partition I/II	O(m·n) 或更高	O(m·n)

推荐刷题顺序：

1. 打基础：Find Pivot Index/Find Pivot Index.cpp) → Number of Ways to Split Array/Number of Ways to Split Array.cpp)（掌握"前缀 + 总和求两侧和"）；
2. 区间查询：Count Vowel Strings in Ranges/Count Vowel Strings in Ranges.cpp) → K Radius Subarray Averages/K Radius Subarray Averages.cpp)；
3. 哈希进阶：Continuous Subarray Sum/Continuous Subarray Sum.cpp) → Contiguous Array/Contiguous Array.cpp) → Make Sum Divisible by P/Make Sum Divisible by P.cpp)（同一模式反复训练）；
4. 差分与混合：Range Addition/Range Addition.cpp) → Grid Game/Grid Game.cpp) → 二维前缀和系列。

每一份源码文件头部都标注了 Leetcode 链接、考察公司（如 Find Pivot Index 标注 Amazon/Adobe/Coupang，Continuous Subarray Sum 标注 Amazon/Facebook/Paytm）与讲解视频信息，便于按图索骥做针对性复习。掌握上述三个套路加一个进阶方向，前缀和专题的大部分面试题都能在短时间内定位到对应模板。

【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo