快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

前缀和，实际上是一种非常简单的动态规划，通过预处理前缀和数组，以空间换时间，提高运行效率。

一、一维前缀和

---

思路：

1. 状态表示：dp[i] 为 [1,i] 区间的前缀和（为了方便表示，下标从1开始）
2. 状态转移方程：dp[i] = dp[i-1] + v[i];
3. 使用前缀和数组：dp[r] - dp[l-1]（表示从l到r的区间和）

int main()
{int n, q, l, r;cin >> n >> q;vector<int> v(n+1);vector<long> dp(n+1);for(int i=1; i<=n; ++i){cin >> v[i];dp[i] = dp[i-1] + v[i];}while(q--){cin >> l >> r;cout << dp[r] - dp[l-1] <<endl;}return 0;
}

二、二维前缀和

---

思路：

1. 状态表示：dp[i][j] 为 (1,1) 到 (i, j) 区间的前缀和
2. 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1] + vv[i][j] - dp[i-1][j-1];
3. 使用前缀和数组：dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

int main()
{int m, n, q;cin >> m >> n >> q;vector<vector<int>> vv(m+1, vector<int>(n+1));vector<vector<long long>> dp(m+1, vector<long long>(n+1));       for(int i=1; i<m+1; ++i){for(int j=1; j<n+1; ++j){cin >> vv[i][j];dp[i][j] = dp[i-1][j] + dp[i][j-1] + vv[i][j] - dp[i-1][j-1];}}while(q--){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;}return 0;
}

三、寻找数值的中心下标

---

思路：

1. 创建前缀和数组f 和 后缀和数组g
2. 状态表示：f[i]代表[0,i-1]区间的前缀和，g[i]代表[i+1,n-1]区间的后缀和
3. f[i] = f[i-1] + nums[i-1]; g[i] = g[i+1] + nums[i+1];

class Solution
{
public:int pivotIndex(vector<int>& nums){int n = nums.size();vector<int> f(n), g(n);for(int i=1; i<n; ++i)f[i] = f[i-1] + nums[i-1];for(int i=n-2; i>=0; --i)g[i] = g[i+1] + nums[i+1];for(int i=0; i<n; ++i)if(f[i] == g[i])return i;return -1;}
};

四、除自身以外数组的乘积

---

思路：

1. 创建前缀积数组f 和 后缀积数组g
2. 状态表示：f[i]代表[0,i-1]区间的前缀积，g[i]代表[i+1,n-1]区间的后缀积
3. f[i] = f[i-1] * nums[i-1]; g[i] = g[i+1] * nums[i+1];

class Solution
{
public:vector<int> productExceptSelf(vector<int>& nums){int n = nums.size();vector<int> f(n, 1), g(n, 1), ans(n);for(int i=1; i<n; ++i)f[i] = f[i-1] * nums[i-1];for(int i=n-2; i>=0; --i)g[i] = g[i+1] * nums[i+1];for(int i=0; i<n; ++i)ans[i] = f[i] * g[i];return ans;}
};

五、和为k的子数组

---

思路：前缀和 + 哈希表

1. 状态表示：dp[i] 代表以i为结尾的区间中和为k的子数组个数
2. 在以i为结尾的区间中，寻找和为dp[i]-k的前缀和，统计个数
3. 无需创建前缀和数组，只需用sum变量维护即可
4. 为了快速查找，创建哈希表countMap存储前缀和
5. 处理边界（sum == k）：countMap[0] = 1;
6. 先统计，再将当前前缀和存入哈希表

class Solution
{
public:int subarraySum(vector<int>& nums, int k){unordered_map<int, int> countMap;countMap[0] = 1;int sum = 0, count = 0;for(auto n : nums){sum += n;if(countMap.count(sum-k)) count += countMap[sum-k];++countMap[sum];}return count;}
};

六、和可被k整除的子数组

---

思路：前缀和 + 哈希表

1. 本题与上题思路类似
2. 同余定理：（a-b）% k == 0 等价于 a%k == b%k
3. （sum-x）% k == 0 等价于 sum%k == x%k（x为之前的前缀和）
4. 正负取模统一：(sum % k + k) % k
5. 创建哈希表countMap存储前缀和的余数

class Solution
{
public:int subarraysDivByK(vector<int>& nums, int k){unordered_map<int, int> countMap;countMap[0] = 1;int sum = 0, count = 0;for(auto n : nums){sum += n;int target = (sum % k + k) % k;if(countMap.count(target)) count += countMap[target];++countMap[target];}return count;}
};

七、连续数组

---

思路：前缀和 + 哈希表

1. 将0改成-1，转化为和为0的子数组
2. 哈希表存储<前缀和，长度>
3. 处理sum == k的边界情况：countMap[0] = -1；
4. 哈希表中只存当前值对应长度最短的前缀和（为了求最长的子数组）

class Solution
{
public:int findMaxLength(vector<int>& nums){//转化：和为0的子数组unordered_map<int, int> countMap;//存储<前缀和,长度>countMap[0] = -1;//处理sum == k的边界情况int sum = 0, len = 0, n = nums.size();for(int i=0; i<n; ++i){sum += nums[i] == 0 ? -1 : 1;//将0变成-1，才能转化if(countMap.count(sum)) len = max(len, i-countMap[sum]);else countMap[sum] = i;//存在代表下标更小，不用更新；不存在才要插入}return len;}
};

八、矩阵区域和

---

思路：

1. 二维前缀和
2. 因为dp矩阵下标从1开始，而原始矩阵下标从0开始，所以注意下标映射关系
3. 为了防止越界，求坐标时用max和min函数与边界比较

class Solution
{
public:int dp[110][110] = {0};vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k){int m = mat.size(), n = mat[0].size();vector<vector<int>> ans(m, vector<int>(n));//预处理前缀和矩阵for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];}}//使用前缀和矩阵int x1 = 0, y1 = 0, x2 = 0, y2 = 0;for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){x1 = max(0, i-k) + 1, y1 = max(0, j-k) + 1;x2 = min(m-1, i+k) + 1, y2 = min(n-1, j+k) + 1;ans[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];}}return ans;}
};

总结

前缀和，以空间换时间，时间复杂度为O(N)，只需常数次遍历即可。

• 小技巧：前缀和数组下标从1开始，可以忽略很多边界情况~

前缀和的模板不用死记硬背，需要根据题目要求变化，现场推导即可。

真诚点赞，手有余香