网页前端做购物网站的实训报告,西安网站设计开发,微信公众号免费开通,网站企业网站建设需求文档目录 题目一#xff1a;一维前缀和[模版]
题目二#xff1a;二维前缀和[模版]
题目三#xff1a;寻找数组的中心下标
题目四#xff1a;除自身以外数组的乘积
题目五#xff1a;和为K的子数组
题目六#xff1a;和可被K整除的子数组
题目七#xff1a;连续数组
题…目录 题目一一维前缀和[模版]
题目二二维前缀和[模版]
题目三寻找数组的中心下标
题目四除自身以外数组的乘积
题目五和为K的子数组
题目六和可被K整除的子数组
题目七连续数组
题目八矩阵区域和 题目一一维前缀和[模版] 示例1
输入
3 2
1 2 4
1 2
2 3
输出
3
6 题目要求是给一个数组需要注意的是下标是从1开始
查询时给下标l和r返回下标从l到下标为r的元素的和
也就是如果数组arr是[2, 4, 6]那么查询时如果是1 2那就返回6(24)如果是2 3就返回10(46)如果是1 3就返回12(246)
解法一暴力解法
暴力解法很简单即就是题目需要求哪段区间的和那我就从这个区间的开始一直加到这个区间的结尾即可
时间复杂度O(N*q)
假设每次询问的查询范围都是从头找到尾所以是O(N)的而q次询问所以是O(q)嵌套起来就是O(N*q)
而这道题N和q的范围都是从1到10^5的最差的情况时间复杂度是10^10是绝对会超时的 解法二前缀和
前缀和快速求出数组中某一个连续区间的和
这里的快速指查找时间复杂度为O(1)但是预处理一个前缀和数组的时间复杂度为O(N)所以使用前缀和后时间复杂度变为O(N) O(q)了之所以不是相乘是因为这两个过程并没有嵌套在一起进行
要想使用前缀和分为下面两步
①预处理出来一个前缀和数组
数组有几个元素前缀和数组dp就有几个元素
dp[i]就表示[1, i]区间内所有元素的和
也就是如果数组arr是[1, 2, 3]那么dp数组就是[1, 3, 6]
这里可以优化的一点是每次算前i个数的和不需要从1开始加从i-1开始加即可因为i-1位置的元素就表示前i-1个元素的和
所以dp[i]的公式是dp[i] dp[i1] arr[i]
②使用前缀和数组
使用前缀和数组也很简单
即如果查找的是3~5区间的和那么只需要使用dp[5] - dp[2]即就是下标为1~5的和减去1~2的和算出来就是3~5的和了
即就是查找[l, r]区间的和则dp[r] - dp[l - 1]即可
下面讲个细节问题为什么下标要从1开始计数
如果计算的是计算的是前两个元素的和公式就变为了dp[2] - dp[-1]这就会导致越界访问了所以这种情况还需要处理边界情况麻烦一些
而如果下标是从1开始的那么如果计算的是前两个元素的和就是dp[2] - dp[0]我们只需将dp数组中dp[0]的值置为0就能完美解决这个问题
代码如下
#include iostream
#include vector
using namespace std;int main() {int n 0,q 0;cin n q;//读入数据vectorint arr(n1);vectorlong long dp(n1);//防止溢出//预处理出来一个前缀和数组for(int i 1; i arr.size(); i){cin arr[i];dp[i] dp[i-1] arr[i];}//使用前缀和数组int l 0, r 0;while(q--){cin l r;cout dp[r] - dp[l-1] endl;}return 0;
} 题目二二维前缀和[模版] 示例1
输入
3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4
输出
8
25
32上述题目一是一维的前缀和题目二是二维的前缀和
就以示例一来说明题意
第一行的 3 4 3表示有一个3行4列的矩阵查询次数是3次
3行4列的矩阵为接下来输入的3行数据即 最后三行就表示所查询的三次内容前两个数字表示一个坐标后两个数字表示一个坐标
即1 1 2 2就表示(1,1)到(2,2)的这个矩形范围所有值的和即下图红色区域 解法一暴力解法
每次询问时都给出整个区间所有元素的和因为是m行n列q此询问所以时间复杂度是O(m*n*q)因为每次询问最差情况都要遍历数组一遍是O(m*q)而询问q次是嵌套关系所以是O(m*n*q)
当然了在看到这个时间复杂度后我们就很容易可以判断出来这个时间肯定超时了所以接下来看解法二 解法二前缀和
同样是分为两步
①预处理出前缀和矩阵
同样重新创建一个和原始矩阵相同规模的矩阵不同的是新矩阵dp每一个位置dp[i, j]表示的含义是从[1, 1]到[i, j]这个位置所有元素的和
例如下图如果想求这个矩阵中所有元素的和那么可以分为下面四部分 我们加入想求[1, 1]到[i, j]位置所有元素的和只需要求A B C D即可也就是将ABCD这四个区域的元素之和相加但是A好求B、C不太好求所以可以退而求其次求A B和A C的值此时多加了一遍A只需最后减去即可所以
dp[i,j] (A B) (A C) D - A dp[i][j-1] dp[i-1][j] arr[i,j] - dp[i-1][j-1]
此时求dp[i,j]的时间复杂度就是O(1)的
②使用前缀和矩阵
所以按照上面的思想如果想要求[x1, y1] ~ [x2, y2]的区域的元素和也就是下面的D区域 此时求D区域就可以整体的ABCD再减去ABC但是单独的B和C不好算所以依旧使用AB和BC来计算因为多减了一次A所以最后再加上多减的那个A即可公式即为
dp[x2, y2] - dp[x1-1, y2] - dp[x2, y1-1] dp[x1-1, y1-1]
根据上图可以轻松写出
由于需要先构建m行n列前缀和数组dp所以时间复杂度是O(m*n)又因为每次查询只需要套一个公式所以时间复杂度为O(1)需要查询q次所以前缀和的时间复杂度为O(m*n) O(q)
上述第一个公式用于预处理出前缀和矩阵第二个公式用于使用前缀和矩阵 代码如下
#include iostream
#include vector
using namespace std;int main()
{//输入数据int n 0,m 0,q 0;cin n m q;vectorvectorint arr(n1,vectorint(m1));for(int i 1; i n; i)for(int j 1; j m; j)cin arr[i][j];//预处理前缀和矩阵vectorvectorlong long dp(n1,vectorlong long(m1));//long long防止溢出for(int i 1; i n; i)for(int j 1; j m; j)dp[i][j] dp[i-1][j] dp[i][j-1] arr[i][j] - dp[i-1][j-1];//使用前缀和矩阵dpint x1 0, y1 0, x2 0, y2 0;while(q--){cin x1 y1 x2 y2;cout (dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]) endl;}return 0;
} 题目三寻找数组的中心下标
给你一个整数数组 nums 请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端那么左侧数之和视为 0 因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标应该返回 最靠近左边 的那一个。如果数组不存在中心下标返回 -1 。
示例 1
输入nums [1, 7, 3, 6, 5, 6]
输出3
解释
中心下标是 3 。
左侧数之和 sum nums[0] nums[1] nums[2] 1 7 3 11
右侧数之和 sum nums[4] nums[5] 5 6 11 二者相等。示例 2
输入nums [1, 2, 3]
输出-1
解释
数组中不存在满足此条件的中心下标。
示例 3
输入nums [2, 1, -1]
输出0
解释
中心下标是 0 。
左侧数之和 sum 0 下标 0 左侧不存在元素
右侧数之和 sum nums[1] nums[2] 1 -1 0 。 解法一暴力解法
每次枚举一个位置都去将这个位置的左边和右边的元素都累加去比较总和是否相同这里的暴力解法的时间复杂度是O(N^2)的
因为枚举下标是O(N)求和也是O(N)所以是时间复杂度是O(N^2) 解法二前缀和
此题使用的依旧是前缀和的思路与前面不同的是此题要求中心下标的左边元素和右边元素相加的和是相同的所以这里可以引出前缀和数组 f 和后缀和数组 g
这里的前缀和数组的定义与前面的前缀和数组的定义是不同的并不包含当前位置的值所以也就进一步的说明前缀和数组只是一个思想并不是一个固定的格式
f[i] 表示从0加到i-1位置的元素和g[i] 表示从i1加到n-1位置的元素和
同样是分为下面的两步
①预处理出前缀和、后缀和数组
首先我们明白在此题中f[i]表示 0 ~ i - 1 位置的元素的和所以f[i-1]就是0~i-2位置的元素的和还差一个nums[i-1]再加上即可g[i]同理可得f[i] f[i-1] nums[i-1] g[i] g[i1] nums[i1]
②使用前缀和、后缀和数组
在上面预处理出前缀和与后缀和数组后只需枚举每个下标时判断f[i]与g[i]是否相等即可如果相等就表示该下标是数组的中心下标
下面是此题需要注意的两个细节问题
第一、f[0]与g[n-1]都需要提前处理因为如果不处理f[0]的公式会出现f[-1]g[n-1]的公式会出现g[n]这两种情况都是导致越界访问
第二、预处理前缀和数组需要从左向右处理而预处理后缀和数组则需要从后向前处理因为前缀和数组计算时每一个位置都需要前一个位置的值而后缀和数组每一个位置都需要后一个位置的值 代码如下
class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();vectorint f(n);vectorint g(n);//预处理前缀和数组f从下标1开始下标0默认值是0for(int i 1; i n; i)f[i] f[i-1] nums[i-1];//预处理后缀和数组g从下标n-2开始下标n-1默认值是0for(int i n - 2; i 0; i--)g[i] g[i1] nums[i1];//使用数组for(int i 0; i n; i)if(f[i] g[i]) return i;return -1;}
}; 题目四除自身以外数组的乘积
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums [-1,1,0,-3,3]
输出: [0,0,9,0,0] 此题题意是比较好理解的 例如示例一数组nums元素是1、2、3、4返回一个数组answer在数组answer中每一个元素的值都是nums中除了该位置的数外其余所有元素的乘积如下所示
nums元素是[1, 2, 3, 4]所以answer数组中的第一个元素值为2*3*424第二个元素值为1*3*412第三个元素值为1*2*48第四个元素的值为1*2*36
所以answer数组的元素就为[24, 12, 8, 6]
解法一暴力解法
暴力解法也很简单依次枚举每个位置然后再求除了该位置外的所有元素的乘积时间复杂度是O(N^2)的
因为枚举每个位置的时间复杂度是O(N)而其中还需要嵌套一个循环是遍历其余元素求其余元素的乘积时间复杂度也是O(N)所以总的时间复杂度是O(N^2) 解法二前缀积 后缀积
此题同样是需要使用前缀和的思想但是每道题的前缀和处理思路都是根据实际情况来定的此题中需要求一个answer数组使得该数组的每一个元素的值都是nums数组中其余元素的乘积
所以如果要求i位置的值就需要知道 0 ~ i-1 位置的元素的乘积以及 i1 ~ n-1 位置的元素的乘积所以此题实际的解法可以称之为前缀积
根据上述的描述我们可以知道想要得到所需的answer数组需要 i 下标之前的前缀积和 i 下标之后的后缀积
同样是分为下面的两步
①预处理出前缀积、后缀积数组
前缀积数组用 f 表示后缀积数组用 g 表示
f[i] 表示[0, i-1]区间内所有元素的积
f[i] f[i-1] * nums[i-1]
g[i] 表示[i1, n-1]区间内所有元素的积
g[i] g[i1] * nums[i1]
②使用前缀积、后缀积数组
由于此题所要求的是得出一个answer数组所以只需创建出一个大小与nums相同的数组数组中每个元素都使用 f[i] * g[i]来得出最后的值
同样这里也有需要注意的细节问题
与上一题一样f[0] 和 g[n-1] 都有可能出现越界访问的问题
因为 f[1] f[0] * nums[0]而f[1]本身就应该等于 nums[0]1乘任意一个数还等于这个数所以这里初始化 f[0] 为1g[n-1]同理可得也初始化为1 代码如下
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint answer(n);//预处理前缀积数组 f 和后缀积数组 gvectorint f(n), g(n);f[0] g[n-1] 1; // 处理细节问题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[i1] * nums[i1];//使用前缀积和后缀积数组for(int i 0; i n; i)answer[i] f[i] * g[i];return answer;}
}; 题目五和为K的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1
输入nums [1,1,1], k 2
输出2示例 2
输入nums [1,2,3], k 3
输出2 解法一暴力解法
此题看题意很容易想出暴力解法即从第一个位置开始依次向后枚举一直累加因为可能存在负数所以每次都需要加到最后一个元素第一个位置累加完毕就从第二个位置加加到最后一个元素位置直到最后一个元素
暴力枚举可以将数组中可能存在的子数组枚举一遍每次判断子数组的元素和是否等于k从而解答此题
暴力枚举的时间复杂度是O(N^2)
根据上述所说可能存在负数的情况所以这里的数组是不具备单调性的所以也就不能使用双指针(滑动窗口)优化 解法二前缀和 哈希表
想要使用前缀和的思想我们可以将子数组转变为以 i 位置为结尾的子数组暴力解法是以 i 位置为开头的所有子数组这两种遍历方式没有区别一个是从前向后遍历一个是从后向前遍历的
之所以使用以 i 结尾是因为这样可以更好的使用前缀和的思想因为此时可以预处理出前缀和数组sumsum[i]就表示 i 之前的所有元素的和 因为需要找元素之和为k的子数组而如果我们以i为结尾从i开始遍历向前找和为k的子数组那和暴力解法没区别所以此时可以转换思路
寻找和为k的子数组当枚举到 i 位置后我们可以根据sum[i]知道以 i 位置为结尾的数组前缀和是多少那么想找到一个子数组的元素和为k可以转换为 当我们枚举到以 i 位置为结尾时想找一个子数组它的前缀和为sum[i] - k即可如果能够找到一个子数组的前缀和为sum[i] - k那么就变相的说明i之前的数组中存在和为k的子数组相当于将i结尾的数组分为了两部分一部分是和为k的子数组一部分是和为sum[i] - k的子数组 也就是说我们想找和为k的A数组转化思路后变为找到和为sum[i]-k的B数组也就相当于找到了和为k的A数组 即需要找到在[0, i-1]这个区间中有多少个前缀和为 sum[i] - k的子数组
那么在了解这个思想后我们难道是直接创建一个前缀和数组再找i位置之前有多少个子数组的和等于sum[i] - k吗那么此时这个算法的时间复杂度也是O(N^2)依旧是遍历数组的思路 因为遍历i位置是O(N)再寻找和为sum[i] - k也是O(N)所以时间复杂度也是O(N^2)那么如何巧妙地解决这个问题呢这里就需要用到哈希表这个思想了
哈希表就是用于快速查找某个数的所以我们可以将前缀和插入到哈希表里统计前缀和出现的次数所以哈希表存的就是int, int类型的第一个int存的是前缀和第二个int存的是前缀和出现的次数此时就无需遍历数组寻找和为sum[i] - k的数组只需要找哈希表中sum[i] - k所对应的数字即可 下面是细节问题
①前缀和何时放入哈希表中 是创建出前缀和数组一股脑全放进去吗是不能一开始就全放进哈希表中的因为我们所计算的是 i 位置之前有多少个前缀和等于sum[i] - k如果全放进入是可能会统计到 i 位置之后的某些位置的前缀和数组也可能等于sum[i] - k 因此在计算 i 位置之前哈希表中只保存 0~i-1 位置的前缀和
②不用真的创建出来一个前缀和数组
因为每次dp[i] dp[i-1] nums[i-1]每次只需要知道前一个位置的前缀和即可所以此题中只需使用一个变量sum标记之前的元素前缀和dp[i-1]是多少计算完dp[i]后把sum更新为dp[i]即可所以在计算下一个dp[i]的时候这个sum依旧是计算前的前缀和的值
③整个前缀和等于k的情况
也就是 0~i 这段区域的区间等于k此时如果出现这种情况我们按照上面的描述就会在[0, -1]的区间内寻找但是这个区间并不存在而我们此时是存在这个等于k的情况的所以需要特殊处理这种情况因为整个数组的和为k我们想找的sum[i] - k就变为0了所以此时需要先设置hash[0] 1先在哈希表中存入这种情况 代码如下
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int hash;//统计前缀和出现的次数hash[0] 1; //处理整个数组之和是k的情况int sum 0, ret 0;for(auto it : nums){sum it;//计算当前位置的前缀和if(hash.count(sum - k)) ret hash[sum - k];//统计个数hash[sum];//将当前位置的前缀和放入哈希表中}return ret; }
}; 题目六和可被K整除的子数组
给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的连续、非空 子数组 的数目。
子数组 是数组的 连续 部分。
示例 1
输入nums [4,5,0,-2,-3,1], k 5
输出7
解释
有 7 个子数组满足其元素之和可被 k 5 整除
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]示例 2:
输入: nums [5], k 9
输出: 0首先这道题在做之前先解释两个数学知识
①同余定理
同余定理指的是如果 (a - b) / p k .... 0也就是说 (a - b) 能够整除 k那就存在a%p b%p
证明很简单(a - b) k*p - a b k*p - a % p b % p
因为k*p % p 0所以得出上式
②负数除以整数的情况
举个例子 -4 % 3 -1但是在数学上余数只有正的所以如果想取得正余数余数无论正负数的通用公式如下
(a % p p) % p
因为负数%正数得出的结果是负数如果想要正数就需要加上这个正数又因为可能原本的结果就是正数此时再%这个正数如果原本就是正数的话后面加的这个p就被抵消了 解法一暴力解法
暴力枚举出所有的子数组然后把子数组的和加起来判断是否能被k整除与上一题一样此题依旧是不能使用滑动窗口来做优化的因为可能存在负数数组不是单调的
解法二前缀和 哈希表
这道题和上一题同样的思想使用前缀和 哈希表完成
同样是求i之前的子数组的元素之和能够整除k也就是下图所示 假设在 i 之前的这段绿色区域的元素之和能够被 k 整除而前面这段红色区域元素之和是 x
所以得到 (sum - x) % k 0根据同余定理可以得到sum % k x % k
所以得到一个结论如果后面的绿色区域能够被 k 整除那么前面的这段红色区域同样能被 k 整除那么也就是说在 [0, i-1] 这个区间内有多少个前缀和的余数是sum % k的就说明有多少个子数组是满足被 k 整除这个条件的
同样需要处理细节问题其他和上一题一样唯一有一个需要注意的是哈希表同样是int, int但是第一个int不是存的前缀和了而是存的前缀和的余数
代码如下
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint ,int hash;hash[0] 1; //特殊情况如果整体的前缀和能被k整除int sum 0, ret 0;for(auto it : nums){sum it; //sum算出当前位置之前的前缀和int ans (sum % k k) % k; //求出修正后的余数if(hash.count(ans)) ret hash[ans]; //统计结果hash[ans];}return ret;}
}; 题目七连续数组
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组并返回该子数组的长度。
示例 1:
输入: nums [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:
输入: nums [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。 首先先看这个题目要求找含有相同数量的0和1的最长连续子数组我们初始看这个题目要求感觉可能半天想不出来解法 但是如果转换一下思路将数组中的0全部换为-1此时就变为了子数组中含有的1和-1的数量相同那如果1和-1的数量相同就说明相加为0了此时就可以和前面的和为k的子数组那道题一样了这道题就变为了和为0的最长子数组了
虽然思想是一样的但是却是有很多细节问题如下所示
①哈希表中存什么
哈希表同样是int, int第一个int存的依然是前缀和但是这里的第二个int存的是下标因为需要知道这里的下标才能算出这里的下标与
②什么时候存入哈希表
和上一题一样都是在计算 i 位置之前哈希表中只保存 0~i-1 位置的前缀和
③如果哈希表中出现重复的sum, i时如何存
存的是第一次出现的值因为如下图所示绿色是符合要求的区域而越早出现的符合要求的点越靠左越靠左绿色的范围就越大 即子数组的长度越长 因为此时符合要求的子数组相加为0所以左边的红色区域的和也就是sum因此符合的点越靠左绿色区域越大即符合要求的子数组长度越长
④默认的整体的数组前缀和为0如何存
因为如果在i位置之前有一个子数组满足条件那么是在0~i-1的区域找满足条件的子数组而此时整个数组都满足题意了那么在前面就没有位置找了所以就变成了在[0, -1]的区间找
当数组整体前缀和为0时我们就需要在-1的位置寻找一个前缀和因为存的是下标所以存的是-1所以此时计算长度时就能够满足这种特殊情况了
⑤最长子数组的长度怎么算 如上图所示绿色区域是所求的子数组长度所以长度计算就为i - j 代码如下
class Solution {
public:int findMaxLength(vectorint nums) {unordered_mapint, int hash;hash[0] -1; //处理特殊情况int sum 0, ret 0;for(int i 0; i nums.size(); i){sum nums[i] 0 ? -1 : 1;//计算当前位置的前缀和并把0全替换为-1if(hash.count(sum)) ret max(i - hash[sum], ret);//这里需要加else为了保证出现重复的sum只保留第一次的确保子数组长度最长else hash[sum] i;}return ret;}
}; 题目八矩阵区域和
给你一个 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 × n的矩阵再给一个整数k要求每一个位置都向上下左右扩展k个单位(超出的部分不算)扩展后的区域的元素之和就是原位置的元素值以示例一为例 2号位置就是计算红色区域的元素和上面虚线就表示超出的范围忽略 5号位置就是计算蓝色区域的元素和
这道题就很明显是要用到二维前缀和了需要在这里再次提醒二维前缀和不需要背模版只需要画图理解很快就能自己现推一个公式出来理解最重要
对于此题来说给一个坐标(i, j)那么这个坐标所对应需要计算的区域就是从(i-k, j-k)到(ik, jk)此时需要考虑是否会超出矩阵的范围所以做如下处理
x1 max(0, i-k)x2 min(m-1, ik)
y1 max(0, j-k)y2 min(n-1, jk)
上述讲解是用于求answer矩阵的每个位置对应的(x1,y1)和(x2,y2)坐标的但是有一个细节问题需要注意
在使用前缀和时我们为了能够正常使用数组的下标都是从1开始的因为从0开始会出现越界访问的问题而此题的下标是从0开始的所以需要考虑下标的映射关系
题目中所给的mat矩阵是3×3的而我们想正常使用前缀和就得让坐标从1开始也就是相比于mat矩阵多加一行多加一列所以mat和answer就变为下图所示 由于dp数组多了一行一列所以就会有下面这种情况
我们想预处理dp二维数组中的(x, y)位置时需要再mat中找的是(x-1, y-1)位置 并且形成最终的answer数组的(x, y)位置时所需要dp数组中的位置又是(x1, y1)
此时就有两种处理思路
第一种思路在预处理dp数组时在原始的公式中把每一个x1、x2、y1、y2都1这样才能对应到mat二维数组中的元素 但是这样处理比较麻烦每一个位置都需要改
第二种思路将刚刚计算的x1、x2、y1、y2是原始mat矩阵的下标如果想在dp矩阵中找位置每个后面都1即可这样就完成了上述操作比较简便
x1 max(0, i-k)1x2 min(m-1, ik)1
y1 max(0, j-k)1y2 min(n-1, jk)1 代码如下
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(), n mat[0].size();vectorvectorint dp(m1, vectorint(n1));vectorvectorint answer(m, vectorint(n));//预处理前缀和数组dpfor(int i 1; i m1; i)for(int j 1; j n1; j)dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i-1][j-1];//使用前缀和数组for(int i 0; i m; i){for(int j 0; j n; j){int x1 max(0, i-k) 1, y1 max(0, j-k) 1;int x2 min(m-1, ik) 1, y2 min(n-1, jk) 1;answer[i][j] dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] dp[x1-1][y1-1];}}return answer;}
}; 前缀和题目到此结束
