前缀和是一个数组的某项下标之前(包括该元素)的所有数组元素的和，前缀和是一种重要的预处理操作，可以降低查询的时间复杂度。
本文以 leetcode 中算法题为例子多前缀和算法的应用进行说明
前缀和应用举例
01、统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。如果某个 连续 子数组中恰好有 k
个奇数数字，我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目。示例 1：输入：nums = [1,1,2,1,1], k = 3
输出：2 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1]
力扣（LeetCode）第1248道题
同求连续子区间的和，只不过改为了连续子区间的奇数数字个数，同样可以使用前缀和的思路求解。
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
unordered_map<int,int> mp;//记录 奇数个数-次数
mp[0] = 1;
int count = 0,pre = 0;//仅需要记录前一个值即可，不需要用数组记录所有的前缀和
for(int i = 0;i< nums.size();i++)
{
if( nums[i] % 2 == 1)
pre++;//计算前缀和
if(mp.find(pre-k) != mp.end())//前面结果中存在满足条件的前缀和
{
count+=mp[pre-k];
}
mp[pre]++;
}
return count;
}
};02、连续子数组和
给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 的倍数，即总和为 n*k，其中 n
也是一个整数。示例 1: 输入: [23,2,4,6,7], k = 6 输出: True 解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。
力扣（LeetCode）第523道题
求连续子数组的和可以采用前缀和的思路。区间[i,j]的和为k的倍数，即求 nums[j] – nums[i] 差为k的倍数，只要 nums[j] 和
nums[i] 除以k的余数相等即满足需求，因此只要记录每个位置前缀和除以k的余数即可。
本题只需要判断是否存在，对于每个余数只需要记录第一次出现位置即可，初始化前缀和为0的位置下标为-1。
当k = 0时，只要存在两个前缀和相等，则区间和为0，同样满足要求。
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int,int> pre_map;//记录 前缀和%k - 首次位置
int sum = 0;
pre_map[0]=-1;//初始化前缀和为0的下标为-1
for(int i = 0;i < nums.size();i++)
{
sum += nums[i];//前缀和
if( k != 0)
{
sum = sum%k;//对k求余数
}
if( pre_map.find(sum) != pre_map.end())//存在满足条件的前缀和
{
if( i - pre_map[sum] > 1)//判断长度大于1
return true;
}
else
{
pre_map.insert({sum,i});
}
}
return false;
}
};03、每个元音包含偶数次的最长子字符串
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’
，在子字符串中都恰好出现了偶数次。示例 1：输入：s = “eleetminicoworoep” 输出：13 解释：最长子字符串是
“leetminicowor” ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
力扣（LeetCode）第1371道题
在题1248统计「优美子数组」中，统计连续子区间奇数数字出现的次数，本题改为了多个字符出现的次数，同样适用前缀和的思路；在题523连续子数组和中，条件是前缀和是k的整数倍，本题中条件为偶数次，即前缀和是2的整数倍，即两个位置对2求余的结果相等即可。
用二进制数字记录状态：我们可以对每个元音字母都维护一个前缀和的数组，实际上我们数组中保存的是每个前缀和对2的余数，即0和1，因此没必要真的维护5个数组，使用一个二进制数字即可表示当前的组合状态，二进制数字中一位代表一个元音字母的状态。比如 00000表示每个元音字母都没出现。本题需求转换为找两个位置的二进制状态相等。
用异或翻转二进制位：用二进制位表示从开始到当前位置的状态，未出现标记成0，出现一次标记为1，再次出现则翻转为0，即某一个位对1进行异或的结果。
哈希表优化：本题中需求为找两个位置的状态相同，并且距离最远。只需要记录每个位置首次出现的位置即可，不断的找相同的状态，越靠后出现的离的越远。
class Solution {
public:
int findTheLongestSubstring(string s) {
int res = 0;//保存返回结果
s = '#'+s;//前置添加一个固定字符，初始化-1的位置
unordered_map<int,int> mp;//每种状态首次出现的位置
string str_temp = "aeiou";//同二进制数字中位的位置
int pre = 0;//前缀状态，初始化为00000
for(int i = 0;i < s.length();i++)
{
if( s[i] == str_temp[j])
pre = pre^(1 << (4 - j)) ;//对相应位置的状态和1进行异或，0变0、0变1
}
if( mp.find(pre) != mp.end())//状态相等
{
res = max(res,i-mp[pre]);//更新最远距离
}
else
{
mp[pre] = i;//记录首次出现的位置
}
}
return res;
}
};
04、二维区域和检索-矩阵不可变
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。示例: 给定
matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7],
[1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
力扣（LeetCode）第304题
先构造前缀和，然后可以O(1)计算给出任意子矩阵的和。
class NumMatrix {
public:
vector<vector<int>> presum;//记录前缀和
int rowcount =0;
int colcount = 0;
NumMatrix(vector<vector<int>>& matrix) {
rowcount = matrix.size();
if( rowcount == 0 )
return;
else
colcount = matrix[0].size();
if(colcount == 0 ) return;
presum = vector(rowcount,vector(colcount,0));//初始化前缀和数组
//构造前缀和数组，presum[i][j] = nums[i][j] + presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1]
for(int i =0;i < rowcount;i++)
{
for(int j = 0;j < colcount;j++)
{
presum[i][j] = matrix[i][j];
if( i-1 >= 0) presum[i][j] += presum[i-1][j] ;
if( j-1 >= 0) presum[i][j] += presum[i][j-1] ;
if( i-1>= 0 && j-1 >= 0) presum[i][j] -= presum[i-1][j-1] ;
}
}
}
int sumRegion(int row1, int col1, int row2, int col2)
{
if(rowcount == 0 || colcount == 0) return 0;
//子矩阵和公式：presum[row2][col2] - presum[row1-1][col2] - presum[row2][col1-1] +presum[row1-1][col1-1]
int res = presum[row2][col2];
if( row1 -1 >=0) res -= presum[row1-1][col2];
if( col1 -1 >=0) res -= presum[row2][col1-1];
if(row1 -1 >= 0 && col1-1 >=0 )
res += presum[row1-1][col1-1];
return res;
}
};
/**
*Your NumMatrix object will be instantiated and called as such: *
NumMatrix* obj = new NumMatrix(matrix); int param_1 = obj->sumRegion(row1,col1,row2,col2);
声明：本站稿件凡恩品牌资讯以外部分类目资讯转载来自于互联网，如有疑义请联系我们删除。
