wordpress 密码验证失败,深圳做seo有哪些公司,电子商务网站建设读书笔记,网站排行榜上升代码【前缀和的核心思想是预先处理数组来快速计算任意子数组的和#xff0c;基本上用于数组和序列问题。】
前缀和算法具体步骤 构造前缀和数组#xff1a; 给定一个数组nums#xff0c;其前缀和数组prex定义为prex[i]表示为数组nums从起始位置到第i个位置的元素累加和。构建前…【前缀和的核心思想是预先处理数组来快速计算任意子数组的和基本上用于数组和序列问题。】
前缀和算法具体步骤 构造前缀和数组 给定一个数组nums其前缀和数组prex定义为prex[i]表示为数组nums从起始位置到第i个位置的元素累加和。构建前缀和公式 p r e x [ i ] n u m s [ i ] ( i 0 ) p r e x [ i ] p r e x [ i − 1 ] n u m s [ i ] ( i 0 ) prex[i] nums[i] \quad (i 0) \\ \\ prex[i] prex[i-1] nums[i] \quad (i 0) prex[i]nums[i](i0)prex[i]prex[i−1]nums[i](i0) 快速计算子数组和 一旦前缀和数组构建完成就可以快速计算任意子数组nums[i...j]的元素累加和。 s u m ( n u m s [ i . . . j ] ) p r e x [ j ] − p r e x [ i − 1 ] ( i 0 ) sum(nums[i...j]) prex[j] - prex[i-1] \quad(i 0) sum(nums[i...j])prex[j]−prex[i−1](i0) 当i 0时子数组和也就是nums[0]。
我们前面介绍过【滑动窗口算法】滑动窗口算法也是基本用于数组和序列问题的所以我们把【前缀和算法】与【滑动窗口算法】放在一起研究也当作对滑动窗口算法的复习。
简要复习一下滑动窗口算法的步骤
【滑动窗口算法的核心思想就是维护一个固定长度的窗口在数组或序列上滑动以满足某些条件。通常用于解决最大子数组和、最小子数组和等问题。】 初始化窗口 设置窗口的起始和结束指针。 滑动窗口 移动窗口的起始和结束指针依据问题的要求调整窗口的大小维护窗口的状态例如窗口内元素的和最大值最小值等。 [!TIP] 之前我们分析滑动窗口算法的时候就提到过选择哪种数据结构来存储数据需要根据【窗口内的数据以及数据的处理形式】来考虑。 比如 如果需要记录窗口中各字符以及各字符出现的次数就用哈希表。 我们通过一个例子看深入了解一下前缀和算法
LeetCode560 和为 K 的子数组 给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1
输入nums [1,1,1], k 2
输出2示例 2
输入nums [1,2,3], k 3
输出2提示
1 nums.length 2 * 104-1000 nums[i] 1000-107 k 107 暴力解法
既然是找满足条件的子数组个数那我们可以枚举所有的子数组然后选出符合条件的子数组就行了。
int subarraySum(vectorint nums, int k) {int size nums.size();int result 0;for (int left 0; left size; left) {for (int right left; right size; right) {//这个时候窗口为 nums[left...right]int sum 0;int cur left;while (cur right) {sum nums[cur];cur;}if (sum k)result;}}return result;
}暴力解法就是这么通俗易懂找出每个子串然后对每个子串单独进行分析就行了。但是暴力解法找子串的时间复杂度是 O ( N 2 ) O(N^2) O(N2),时间复杂度太高了所以我们需要思考另一种解法。
前缀和分析思路
联想刚刚学到的前缀和表示子数组我们知道子数组nums[i...j]之和不就是prex[j] - prex[i-1]嘛。也就是说和为 K 的子数组满足等式 p r e x [ j ] − p r e x [ i − 1 ] K prex[j] - prex[i-1] K prex[j]−prex[i−1]K
但是按照这个等式思路我们只是利用了前缀和来方便找出各个子串的和罢了还是要变动i,j两个变量来查找和为 K 的子数组时间复杂度还是 O ( N 2 ) O(N^2) O(N2)我们得到目标是什么是要降低时间复杂度。很容易想到既然变动两个变量的时间复杂度为 O ( N 2 ) O(N^2) O(N2),那我们就试试只变动一个变量我们对上面公式进行变换 p r e x [ i − 1 ] p r e x [ j ] − K prex[i-1] prex[j] - K prex[i−1]prex[j]−K
从这个公式我们清楚如果子串最右边字符的位置j确定那么要想找到【和为 K 的子数组】的个数只需找到前缀和数组中0,1,...j-1这些位置对应的值中有几个值等于 K − p r e x [ j ] K-prex[j] K−prex[j], 如果我们把这个查找的实践复杂度降为 O ( 1 ) O(1) O(1)那么总体的时间复杂度只消耗在j的变动上了嘛也就降为了 O ( N ) O(N) O(N)。
怎么实现这个查找呢和滑动窗口算法一样面对不同的数据组织和变动情况我们要选择合适的数据结构来帮助我们存储和查找数据。在这个题目中因为要存储0,1,...,j-1的前缀和以及前缀和出现的次数所以我们使用哈希表来存储数据键代表j之前的各个前缀和值代表此前缀和对应的数组出现的次数。
分析了这么多最后我们只要移动j就行了只需要对数组遍历一次。
我们给出前缀和解法
int subarraySum(vectorint nums, int k) {//计数器存储j之前数组和以及数组和出现的次数unordered_mapint,int mp;mp[0]; //数组为空和自然为0int prex[nums.size()];int result 0;for(int j 0; j nums.size(); j){if(j 0){prex[j] nums[j];//查找j之前的数组和有几个满足条件if(mp.count(prex[j] - K)){result mp[prex[j] - K];}mp[prex[j]];continue;}prex[j] prex[j-1] nums[j];if(mp.count(prex[j] - K)){result mp[prex[j] - K];}mp[prex[j]];}return result;
}这段代码便是我们利用【前缀和】和【哈希表】得到的解法时间复杂度是降低了空间复杂度能降低吗
复盘这段代码我们发现在循环里第j次循环只用到了prex[j]并不会用到前面的prex[0...j-1]所以我们不用再花费 O ( N ) O(N) O(N)的空间复杂度去维护前缀和数组prex[]直接用一个变量prex表示prex[j]即可。
改造后的代码
int subarraySum(vectorint nums, int k) {//计数器存储j之前数组和以及数组和出现的次数unordered_mapint,int mp;mp[0]; //数组为空和自然为0int prex 0;int result 0;for(int num : nums){prex num;if(mp.count(prex - K)){result mp[prex - K];}mp[prex];}return result;
}到这里你基本上掌握了前缀和的思想了但是要注意的是 [!IMPORTANT] 前缀和只是我们用来表示子数组的一种方法而已遇到具体问题我们要找出问题的本质子数组间有什么关系最好能找出具体公式出来比如这道【和为 K 的子数组】题目我们就是找出了公式 p r e x [ j ] − p r e x [ i − 1 ] K prex[j] - prex[i-1] K prex[j]−prex[i−1]K 之后对这个公式进行分析进行合适的变换。 1248 454
【我们再看两道题来巩固一下【前缀和】与其他数据结构结合的算法思想】
LeetCode523 连续的子数组 一个 好的子数组 是
长度 至少为 2 且子数组元素总和为 k 的倍数。
注意
子数组 是数组中 连续 的部分。如果存在一个整数 n 令整数 x 符合 x n * k 则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。
示例 1
输入nums [23,2,4,6,7], k 6
输出true
解释[2,4] 是一个大小为 2 的子数组并且和为 6 。示例 2
输入nums [23,2,6,4,7], k 6
输出true
解释[23, 2, 6, 4, 7] 是大小为 5 的子数组并且和为 42 。
42 是 6 的倍数因为 42 7 * 6 且 7 是一个整数。示例 3
输入nums [23,2,6,4,7], k 13
输出false提示
1 nums.length 1050 nums[i] 1^090 sum(nums[i]) 2^31 - 11 k 2^31 - 1 分析过程
这道题算是【和为 K 的子数组】的变式求【和为 K 的整数倍的子数组】我们先考虑迁移【和为 K 的子数组的解法】。
得出公式 p r e x [ j ] − p r e x [ i − 1 ] λ ∗ K p r e x [ i − 1 ] p r e x [ j ] − λ ∗ K prex[j] - prex[i-1] λ*K \\ prex[i-1] prex[j] - λ*K prex[j]−prex[i−1]λ∗Kprex[i−1]prex[j]−λ∗K
解法框架如下
bool checkSubarraySum(vectorint nums, int k) {//计数器存储j之前数组和以及数组和出现的次数unordered_mapint,int mp;mp[0]; //数组为空和自然为0int prex 0;int result 0;for(int num : nums){prex num;if(mp.count(prex - lamda*K)){result mp[prex - lamda*K];}mp[prex];}return result 0;
}我们怎么确定这个 l a m d a lamda lamda呢要枚举 l a m d a lamda lamda的取值并代入吗 l a m d a lamda lamda取值为 0 , . . . , [ p r e x / X ] 0,...,[prex/X] 0,...,[prex/X]。或者遍历mp里的每个键查看prex是否能整除X。
上面的分析只分析了子数组的数组和可能为 K 的倍数子数组的长度至少为 2这个要求我们并没有考虑。和子数组长度有关的话哈希表存储前缀和以及前缀和出现的次数就不能用了因为哈希表里的前缀和nums[0...i]并不能确定是i是什么我们只是将前缀和的值一股脑放进哈希表里而已。
所以我们现在要改变数据存储形式要么使用别的数据结构要么将哈希表里的键值对对应的数据改为其他数据。所以现在我们要体现出【前缀和】以及【前缀和对应的位置nums[0...i](i)】和【出现的次数】。怎么体现呢按照之前思路我们是在遍历prex[j]在遍历的同时将{前缀和:{位置出现次数}}存入哈希表中。
解法如下
bool checkSubarraySum(vectorint nums, int k) {//计数器存储j之前数组和以及数组和出现的次数unordered_mapint,pairint,int mp;mp[0] {-1,1}; //数组为空和自然为0int prex 0;int result 0;for(int j 0;j nums.size();j){prex nums[j];//遍历哈希表查看是否存在这样一个前缀和使得prex与这个前缀和之差是K的倍数,且满足长度大于等于2for(const auto element : mp){if((prex - element.first)% k 0){if(element.second.first j - 1){result element.second.second;}}}mp[prex] {j,mp[prex]1}; //?}return result 0;
}接下来看看二维以及多维的前缀和是如何使用的
二维前缀和
【二维前缀和】和【一维前缀和】一样也是记录前面数组元素的累加和。对于一维而言就是前 0 , 1 , . . . , i − 1 0,1,...,i-1 0,1,...,i−1这些位置对应的元素的累加和二维也是一样前 0 m i , 0 n j , ( m , n ) 0 m i, 0 n j,(m,n) 0mi,0nj,(m,n) 这些位置对应的元素累加和其实也就是以 ( i , j ) (i,j) (i,j) 为右下角的正方形左上方的所有元素之和。同样我们给出二维前缀和数组以及递推公式
二维前缀和具体步骤 构建二维前缀和数组 给定一个二维数组matrix其前缀和数组定义为preSum[i][j]表示以(0,0)为左上角(i,j)为右下角的矩形内所有元素之和。构建二维前缀和公式 p r e S u m [ 0 ] [ 0 ] m a t r i x [ 0 ] [ 0 ] p r e S u m [ 0 ] [ j ] p r e S u m [ 0 ] [ j − 1 ] m a t r i x [ 0 ] [ j ] ( i 0 , j 0 ) p r e S u m [ i ] [ 0 ] p r e S u m [ i − 1 ] [ 0 ] m a t r i x [ i ] [ 0 ] ( i 0 , j 0 ) p r e S u m [ i ] [ j ] p r e S u m [ i − 1 ] [ j ] p r e S u m [ i ] [ j − 1 ] − p r e S u m [ i − 1 ] [ j − 1 ] m a t r i x [ i ] [ j ] ( i 0 , j 0 ) preSum[0][0] matrix[0][0] \\ preSum[0][j] preSum[0][j-1] matrix[0][j]\quad(i 0, j 0)\\ preSum[i][0] preSum[i-1][0] matrix[i][0]\quad(i0,j0)\\ preSum[i][j] preSum[i-1][j] preSum[i][j-1] - preSum[i-1][j-1] matrix[i][j]\quad(i0,j0) preSum[0][0]matrix[0][0]preSum[0][j]preSum[0][j−1]matrix[0][j](i0,j0)preSum[i][0]preSum[i−1][0]matrix[i][0](i0,j0)preSum[i][j]preSum[i−1][j]preSum[i][j−1]−preSum[i−1][j−1]matrix[i][j](i0,j0) 优化后的二维前缀和数组 我们发现上面的二维前缀和公式过于麻烦需要分类讨论四种情况这四种情况都是边界处的情况。所以我们现在弱化边界在边界之外再套一层在原来的二维数组左上方套一层套上的每一个元素都是 0这样就不会影响前缀和数组的数值。 优化后的数组定义preSum[i][j]表示以(0,0)为左上角(i-1,j-1)为右下角的矩形内所有元素之和。preSum[0][0...n],preSum[0...n][0]这些元素都赋值 0这也就是我们上面说的套上一层辅助数据这些数据都是 0。二维前缀和公式 p r e S u m [ i ] [ j ] p r e S u m [ i − 1 ] [ j ] p r e S u m [ i ] [ j − 1 ] − p r e S u m [ i − 1 ] [ j − 1 ] m a t r i x [ i − 1 ] [ j − 1 ] ( i 1 , j 1 ) preSum[i][j] preSum[i-1][j] preSum[i][j-1] - preSum[i-1][j-1] matrix[i-1][j-1]\quad(i1,j1) preSum[i][j]preSum[i−1][j]preSum[i][j−1]−preSum[i−1][j−1]matrix[i−1][j−1](i1,j1) 优化后的数组preSum[i][j]对应matrix[i-1][j-1]为右下角的矩形元素累加和。 快速计算区域子矩阵和多维数组叫着有点别扭后面都会用矩阵代替多维数组 得出前缀和矩阵后我们可以利用前缀和矩阵快速计算出子矩阵中元素累加和。如果子矩阵的左上角为(m,n),右下角为(i,j)那么我们可以直接利用公式 S u b M a t r i x S u m p r e S u m [ i ] [ j ] − p r e S u m [ i ] [ n − 1 ] − p r e S u m [ m − 1 ] [ j ] p r e S u m [ m − 1 ] [ n − 1 ] SubMatrixSum preSum[i][j] - preSum[i][n-1] - preSum[m-1][j] preSum[m-1][n-1] SubMatrixSumpreSum[i][j]−preSum[i][n−1]−preSum[m−1][j]preSum[m−1][n−1] 这里是利用了优化后的前缀和数组来进行分析i,j的取值为 1... n 1...n 1...n。
我们来看一道题目充分理解二维前缀和
LeetCode1314 矩阵区域和 给你一个 m x n 的矩阵 mat 和一个整数 k 请你返回一个矩阵 answer 其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和
i - k r i k, j - k c j k 且(r, c) 在矩阵内。
示例 1
输入mat [[1,2,3],[4,5,6],[7,8,9]], k 1
输出[[12,21,16],[27,45,33],[24,39,28]]示例 2
输入mat [[1,2,3],[4,5,6],[7,8,9]], k 2
输出[[45,45,45],[45,45,45],[45,45,45]]提示
m mat.lengthn mat[i].length1 m, n, k 1001 mat[i][j] 100 问题分析
我们很容易看出answer[i][j]表示的就是以[i][j]为中心边长为 2 ∗ k 1 2*k1 2∗k1的正方形内的所有元素之和。对照刚刚讲的二维前缀矩阵这个正方形可以由什么表示呢
int start_i std::max(i-k,0);
int start_j std::max(j-k,0);
int end_i std::min(m-1,ik);
int end_j std::min(n-1,jk);其实这个“正方形”中的元素就是以start_i,start_j为左上角end_i,end_j为右下角的矩形中的所有元素。answer[i][j]存的就是这个矩形中所有元素的累加和嘛。这个累加和我们直接用递推公式就可以得出来 S u b M a t r i x S u m p r e S u m [ e n d i 1 ] [ e n d j 1 ] − p r e S u m [ e n d i 1 ] [ s t a r t j − 1 1 ] − p r e S u m [ s t a r t i − 1 1 ] [ e n d j 1 ] p r e S u m [ s t a r t i − 1 1 ] [ s t a r t j − 1 1 ] SubMatrixSum preSum[end_i1][end_j1] - preSum[end_i1][start_j-11] \\ - preSum[start_i-11][end_j1] preSum[start_i-11][start_j-11] SubMatrixSumpreSum[endi1][endj1]−preSum[endi1][startj−11]−preSum[starti−11][endj1]preSum[starti−11][startj−11]
这里的(i,j)是基于原矩阵matrix的。
现在我们给出最终代码
vector vectorint matrixBlockSum(vector vectorint mat, int k) {int m mat.size();int n mat[0].size();vector vectorint answer(m, vectorint(n));//创建前缀和矩阵int preSum[m 1][n 1];for (int j 0; j n; j) {preSum[0][j] 0;}for (int i 0; i m; i) {preSum[i][0] 0;}//为前缀和矩阵赋值for (int i 0; i m; i) {for (int j 0; j n; j) {preSum[i 1][j 1] preSum[i][j 1] preSum[i 1][j]- preSum[i][j] mat[i][j];}}//为answer矩阵赋值for (int i 0; i m; i) {for (int j 0; j n; j) {int start_i std::max(i-k,0);int start_j std::max(j-k,0);int end_i std::min(m-1,ik);int end_j std::min(n-1,jk);answer[i][j] preSum[end_i 1][end_j 1] - preSum[end_i 1][start_j]- preSum[start_i][end_j 1] preSum[start_i][start_j];}}return answer;
}注意前缀和只是一种求子数组和子矩阵的方法而已当遇到需要求解子数组或者子矩阵的问题时如果需要用到子数组或者子矩阵中的元素可以使用前缀和来表示子数组或者子矩阵。
