《信息学C++知识讲解》：前缀和算法总结(二)

前缀和应用举例

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++)        {            for(int j = 0;j< 5;j++)            {                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); */