【算法一周目】从时光的边缘看世界：前缀和揭示的算法真谛

文章目录

• 1.一维前缀和
• 2.二维前缀和
• 3.寻找数组的中心下标
• 4.除自身以外数组的乘积
• 5.和为k的子数组
• 6.和可被k整除的子数组
• 7.连续数组
• 8.矩阵区域和

1.一维前缀和

题目链接：【模板】一维前缀和

题目描述：

给定一个长度为 n 的整数数组 arr 和 q 个查询，每个查询由两个整数 l 和 r 组成，表示区间 [l, r]。请计算出每个区间内所有元素的和。

示例 1：

• 输入：arr = [1, 2, 3, 4, 5], q = 2, 查询区间为 [(1, 3), (2, 4)]
• 输出：[6, 9]
• 解释：区间 [1, 3] 的元素和为 1 + 2 + 3 = 6，区间 [2, 4] 的元素和为 2 + 3 + 4 = 9。

提示：

• 1 <= n, q <= 100000
• -10000 <= arr[i] <= 10000

解题思路
对于本道题，我们可以提前预处理出一个前缀和数组 d p dp dp ，通过前缀和数组快速求出某个区间所有元素的和。

前缀和数组 d p [ i ] dp[i] dp[i] 表示数组起始位置到第 i i i 个位置的所有元素和。其递推公式我们很容易得出：

• d p [ i ] = d p [ i − 1 ] + a r r [ i ] dp[i] = dp[i-1] + arr[i] dp[i]=dp[i−1]+arr[i]

计算区间 [ l , r ] [l, r] [l,r] 的所有元素的和：

• s u m = d p [ r ] − d p [ l − 1 ] sum = dp[r] - dp[l-1] sum=dp[r]−dp[l−1]

代码实现

#include<iostream>#include<vector>usingnamespace std;intmain(){//处理输入输出int n, q; cin >> n >> q; vector<int>arr(n +1);for(int i =1; i <= n;++i) cin >> arr[i];//预处理dp数组，long long元素类型防止溢出 vector<longlong>dp(n +1);for(int i =1; i <= n;++i) dp[i]= dp[i -1]+ arr[i];int l, r;while(q--){ cin >> l >> r; cout << dp[r]- dp[l -1]<< endl;}return0;}

细节处理：我们开辟前缀和数组时开的空间大小应该比数组的大1（开辟 n + 1 n + 1 n+1 的空间），可以让数组的元素位置与下标一一对应（第一个元素对应下标1位置），帮助我们规避掉像 d p [ 1 ] dp[1] dp[1] 等边界情况。

2.二维前缀和

题目链接：【模板】二维前缀和

题目描述：

给定一个大小为 n × m 的矩阵 matrix 和 q 个查询，每个查询由四个整数 x1, y1, x2, y2 组成，表示一个子矩阵的左上角 (x1, y1) 和右下角 (x2, y2)。请计算出每个子矩阵内所有元素的和。

示例 1：

• 输入：matrix = [[1, 2], [3, 4]], q = 1, 查询区间为 [(1, 1, 2, 2)]
• 输出：[10]
• 解释：子矩阵包含所有元素 1 + 2 + 3 + 4 = 10。

提示：

• 1 <= n, m <= 1000
• -10000 <= matrix[i][j] <= 10000

解题思路

这道题与上一道题类似，我们可以提前预处理出一个前缀矩阵和数组 d p dp dp ， d p [ i ] [ j ] dp[i][j] dp[i][j] 表示矩阵从 [ 1 , 1 ] [1, 1] [1,1] 位置到 [ i , j ] [i, j] [i,j]位置的所有元素和，然后利用 d p dp dp 数组快速求出子矩阵内所有元素的和。

1. 构建前缀和矩阵数组
   • 递推公式： d p [ i ] [ j ] = m a t r i x [ i ] [ j ] + d p [ i ] [ j − 1 ] + d p [ i − 1 ] [ j ] − d p [ i − 1 ] [ j − 1 ] dp[i][j] = matrix[i][j] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] dp[i][j]=matrix[i][j]+dp[i][j−1]+dp[i−1][j]−dp[i−1][j−1]
   • s u m = d p [ x 2 ] [ y 2 ] − d p [ x 1 − 1 ] [ y 2 ] − d p [ x 2 ] [ y 1 − 1 ] + d p [ x 1 − 1 ] [ y 1 − 1 ] sum = dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1] sum=dp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]+dp[x1−1][y1−1]

计算 [ x 1. y 1 ] − > [ x 2 , y 2 ] [x1. y1] -> [x2, y2] [x1.y1]−>[x2,y2] 任意子矩阵的和 s u m sum sum

构建数组时与上题类似，每一行每一列多开一个空间以此来避免边界情况。

代码实现

#include<iostream>#include<vector>usingnamespace std;intmain(){//处理输入数据int n =0, m =0, q =0; cin >> n >> m >> q; vector<vector<int>>vv(n +1,vector<int>(m +1));for(int i =1; i <= n;++i){for(int j =1; j <= m;++j) cin >> vv[i][j];}//预处理矩阵数组, longlong防溢出  vector<vector<longlong>>dp(n +1,vector<longlong>(m +1));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]+ vv[i][j]- dp[i -1][j -1];}//输出int x1, y1, x2, y2;while(q--){ cin >> x1 >> y1 >> x2 >> y2;longlong ret = dp[x2][y2]- dp[x2][y1 -1]- dp[x1 -1][y2]+ dp[x1 -1][y1 -1]; cout << ret << endl;}return0;}

3.寻找数组的中心下标

题目链接：724. 寻找数组的中⼼下标

题目描述：

给你⼀个整数数组 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。

提示：

• 1 <= nums.length <= 10⁴
• -1000 <= nums[i] <= 1000

解题思路
根据题目要求，我们可以预处理出一个前缀和数组 f f f 和后缀和数组 g g g，然后遍历数组通过比较前缀和和后缀和找到中心下标。

1. 前缀和数组
   • f [ i ] f[i] f[i] 表示数组开始位置到 i − 1 i-1 i−1 位置的所有元素和
   • 递推公式： f [ i ] = f [ i − 1 ] + n u m s [ i − 1 ] f[i] = f[i-1]+nums[i-1] f[i]=f[i−1]+nums[i−1]
2. 后缀和数组
   • g [ i ] g[i] g[i] 表示数组 i + 1 i+1 i+1 位置到数组末尾位置的所有元素和
   • 递推公式： g [ i ] = g [ i + 1 ] + n u m s [ i + 1 ] g[i] = g[i+1]+nums[i+1] g[i]=g[i+1]+nums[i+1]

代码实现

classSolution{public:intpivotIndex(vector<int>& nums){//预处理出前缀和、后缀和数组int n = nums.size(); vector<int>f(n);//数组起始位置的左侧for(int i =1; i < n;++i) f[i]= f[i -1]+ nums[i -1]; vector<int>g(n);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;}};

优化解法

上面的解法其实还可以优化，设 n u m s nums nums 的所有元素之和为 S S S ，中心下标为 i i i ， i i i 左边的元素和为 l s u m lsum lsum ，根据左侧元素和与右侧元素和相等有：

• l s u m = S − n u m s [ i ] − l s u m lsum = S-nums[i]-lsum lsum=S−nums[i]−lsum

稍微化简有：

• 2 × l s u m = S − n u m s [ i ] 2\times lsum = S-nums[i] 2×lsum=S−nums[i]

所以我们只需用一个量 l e f t s u m leftsum leftsum 记录当前元素的左侧元素和，根据推导公式判断当前位置是否为中心下标。

优化后的解法时间复杂度从 O ( n ) O(n) O(n) 降到了 O ( 1 ) O(1) O(1) 了。

classSolution{public:intpivotIndex(vector<int>& nums){int sum =0;for(auto e : nums) sum += e;int leftSum =0;for(int i =0; i < nums.size();++i){if(2* leftSum == sum - nums[i])return i; leftSum += nums[i];}return-1;}};

4.除自身以外数组的乘积

题目链接：238. 除自身以外数组的乘积

题目描述：

给你⼀个整数数组 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]

提示：

• 2 <= nums.length <= 10⁵
• -30 <= nums[i] <= 30
• 保证数组 nums 中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

解题思路

与上一题类似，我么先预处理出前缀积数组 f f f 和后缀积数组 g g g ，然后将两者相乘得到除自身元素以外的乘积。

1. 前缀积数组

• f [ i ] f[i] f[i] 表示数组起始位置到第 i − 1 i-1 i−1 位置所有元素的积。
• 递推公式： f [ i ] = f [ i − 1 ] × n u m s [ i − 1 ] f[i]=f[i-1] \times nums[i-1] f[i]=f[i−1]×nums[i−1]

2. 后缀积数组

• g [ i ] g[i] g[i] 表示数组第 i + 1 i+1 i+1 位置到数组末尾位置所有元素的积。
• 递推公式： g [ i ] = g [ i + 1 ] × n u m s [ i + 1 ] g[i]=g[i+1] \times nums[i+1] g[i]=g[i+1]×nums[i+1]

细节： f [ 0 ] = g [ n − 1 ] = 1 f[0] = g[n-1]=1 f[0]=g[n−1]=1，对于这两个数组初始情况需要为1

构建出前缀积与后缀积数组后，我们直接遍历，两者相乘，构建出需要返回的数组 r e t ret ret

代码实现

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

优化解法

我们可以先处理出后缀积 g g g ，用 pre 记录前缀积（初始化为1），然后遍历将 p r e pre pre 乘到 g [ i ] g[i] g[i] 中，同时维护 p r e pre pre ，最后将 g 返回即可。

这种写法相较于上种可以少遍历一次数组，而且题目说到输出数组不被视为额外空间，故时间复杂度为 O ( 1 ) O(1) O(1) 。

classSolution{public: vector<int>productExceptSelf(vector<int>& nums){int n = nums.size(); vector<int>g(n,1);//后缀积for(int i = n -2; i >=0;--i) g[i]= g[i +1]* nums[i +1];//遍历修改g[i]//pre为i位置左侧元素的乘积int pre =1;for(int i =0; i < n;++i){ g[i]*= pre; pre *= nums[i];}return g;}};

5.和为k的子数组

题目链接：560. 和为 K 的子数组

题目描述：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

示例 1：

• 输入：nums = [1,1,1], k = 2
• 输出：2
• 解释：共有两个子数组的和为 2，分别是 [1,1] 和 [1,1]。

示例 2：

• 输入：nums = [1,2,3], k = 3
• 输出：2
• 解释：共有两个子数组的和为 3，分别是 [1,2] 和 [3]。

提示：

• 1 <= nums.length <= 2 * 10⁴
• -1000 <= nums[i] <= 1000
• -10⁷ <= k <= 10⁷

解题思路

根据题目要求，我们需要求出和为 K K K 的子数组的个数。

我们可以使用暴力解法，定义两个指针 i i i 和 j j j ，固定 i i i ， j j j 依次往后遍历，注意，找到符合的数组后， j j j 也要继续遍历，因为以 i i i 为起点的和为 K K K 的子数组不止一个， j j j 遍历完一遍数组后 i i i 往后加一，直到 i i i 遍历完数组，这样就求出和为 K K K 的子数组的个数，但是暴力解法的时间复杂度是 O ( n 2 ) O(n^2) O(n2) ，一定会超时。

对于这道题，我们不能使用滑动窗口，当窗口内出现符合的子数组时，统计个数后窗口的左边端点会前移，因为数组的元素有正有负不满足单调性，这样是会错过一些符合的数组，比如在 [ 1 , − 1 , 0 , 0 , 0 ] [1, -1, 0, 0, 0] [1,−1,0,0,0] 求和为 0 0 0 的子数组的个数。

我们的最优解法是前缀和+哈希表。对于 [ 0 , i ] [0, i] [0,i] 区间的数组，其元素之和为 s u m sum sum ，如果通过哈希表查询到该区间数组和为 s u m − K sum - K sum−K 的子数组的个数，这样就间接知道了 [ 0 , i ] [0, i] [0,i] 区间的数组内和为 K 的子数组的个数。

代码实现

classSolution{public:intsubarraySum(vector<int>& nums,int k){//哈希表记录前缀和及其出现的次数 unordered_map<int,int> hash;//处理区间和为K的特殊情况 hash[0]=1;int sum =0, ret =0;for(int i =0; i < nums.size();++i){//计算[0,i]的前缀和 sum += nums[i];//查找和为sum-k的子数组的个数if(hash.count(sum - k)) ret += hash[sum-k];//将前缀和加入哈希表 hash[sum]++;}return ret;}};

细节处理：

1. 对于前缀和，我们没有必要格外开辟空间来计算，只需要用一个变量 s u m sum sum 去维护即可。
2. h a s h [ 0 ] = 1 hash[0]=1 hash[0]=1 ：和为 0 的子数组出现的次数默认有一次，这是因为区间元素和刚好第一次为 K K K 时，按照我们的算法，需要查找和为 0 0 0 的子数组个数，但是由于整个区间的所有元素和为 K K K ，没有额外剩余的元素去构成和为 0 0 0 的子数组，所以如果没有 h a s h [ 0 ] = 1 hash[0]=1 hash[0]=1 ，哈希表是查找不到和为 0 0 0 的子数组的个数，我们的算法是会遗漏整个区间的和第一次为 K K K 的情况，最后统计出来的和为 K K K 的子数组的个数是会少一个的。

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n) ，哈希表的空间开销

6.和可被k整除的子数组

题目链接：974. 和可被 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

提示：

• 1 <= nums.length <= 3 * 10⁴
• -10⁴ <= nums[i] <= 10⁴
• 2 <= k <= 10^4

解题思路

对于这道题，我们依然使用前缀和+哈希表，但是在此之前先引入下同余定理。

同余定理：

• 如果 ( a − b ) m o d K = = 0 (a-b) \bmod K = = 0 (a−b)modK==0 ，则有 a m o d K = = b m o d K a \bmod K == b \bmod K amodK==bmodK 。

所以整体思路就是对于 [ 0 , i ] [0, i] [0,i] 区间的数组，其元素之和为 s u m sum sum ，对 s u m sum sum 进行取模( m o d K \bmod K modK)余数为 m o d mod mod ，如果通过哈希表查询到该区间内数组和的余数同样为 m o d mod mod 的子数组的个数，这样就间接知道了 [ 0 , i ] [0, i] [0,i] 区间的数组内和可为 K 整除的子数组的个数。

代码实现

classSolution{public:intsubarraysDivByK(vector<int>& nums,int k){//哈希表存储前缀和余数及其出现的次数 unordered_map<int,int> hash;//处理区间元素和刚好被K整除，余数为0的特殊情况 hash[0]=1;int ret =0, sum =0;for(auto e : nums){//计算前缀和 sum += e;//对前缀和取模，注意在C++中，余数可为负//需要换算成非负以免影响结果int mod =(sum % k + k)% k;//查找前缀和的余数为mod的子数组的个数if(hash.count(mod)) ret += hash[mod];//将余数加入哈希表 hash[mod]++;}return ret;}};

代码解析：

1. 哈希表存储的是前缀和的余数及其出现的次数，与上道题不同。
2. h a s h [ 0 ] = 1 hash[0] = 1 hash[0]=1 ：余数为 0 0 0 默认出现次数为 1 1 1 次，是为了处理区间元素和第一次刚好被 K K K 整除的特殊情况，防止答案遗漏。
3. (sum % k + k) % k ：在C++中，余数可以为负数，需要将其调整为正数，不然会影响结果。

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( K ) O(K) O(K) ，哈希表存储余数的额外空间开销。

7.连续数组

题目链接：525. 连续数组

题目描述：

给定一个二进制数组 nums，找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1：

• 输入：nums = [0,1]
• 输出：2
• 说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2：

• 输入：nums = [0,1,0]
• 输出：2
• 说明：[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

提示：

• 1 <= nums.length <= 10⁵
• nums[i] 不是 0 就是 1

解题思路

题目要求我们找含有相同数量的 0 0 0 和 1 1 1 的最长连续子数组的长度，我们可以将0看作成-1，这样问题就转换成了求和为0的子数组最长长度。

解决这道题的思路依然是前缀和+哈希，对于 [ 0 , i ] [0, i] [0,i] 区间的数组，其元素之和为 s u m sum sum ，通过哈希表查询到该区间内数组和同样为 s u m sum sum 的子数组的末尾元素下标，间接求出和为 0 0 0 的子数组长度。

但是需要注意的是，当哈希表中已经存在 s u m sum sum 时，不必更新 s u m sum sum 在哈表中的下标，因为题目要求的是子数组最长长度。

代码实现

classSolution{public:intfindMaxLength(vector<int>& nums){//哈希表存储的是[0,i]区间元素和及其下标i unordered_map<int,int> hash;//处理前缀和刚好为0的情况 hash[0]=-1;int sum =0, ret =0;for(int i =0; i < nums.size();++i){//将数组中的0看待成-1 sum += nums[i]==0?-1:1;//如果前缀和存在则更新结果，不存在再加入哈希表if(hash.count(sum)) ret =max(ret, i - hash[sum]);else hash[sum]= i;}return ret;}};

代码解析：

1. 哈希表存储 [ 0 , i ] [0,i] [0,i] 区间元素和及其下标 i i i 。
2. h a s h [ 0 ] = − 1 hash[0] = -1 hash[0]=−1 ：前缀和为 0 0 0 的子数组下标默认为 − 14 -14 −14 ， 处理处理前缀和第一次为 0 0 0 的特殊情况。

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n) ，哈希表的额外空间开销。

8.矩阵区域和

题目链接：314. 矩阵区域和

题目描述：

给你一个 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.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= mat[i][j] <= 100

解题思路

通过分析题目可以知道，其实就是快速求出子矩阵 [ i − k , j − k ] [i-k, j-k] [i−k,j−k] 到 [ i + k , j + k ] [i+k, j+k] [i+k,j+k] 的所有元素的和，我们可以先预处理出来一个矩阵前缀和数组 d p dp dp ，然后通过矩阵前缀和数组快速求出子矩阵的所有元素和。

1. 构建矩阵前缀和 d p dp dp
   • 开辟空间时多开一行和一列，简化边界情况的处理
   • d p [ i ] [ j ] dp[i][j] dp[i][j] 表示矩阵 m a t mat mat 从 [ 0 , 0 ] [0, 0] [0,0] 到 [ i − 1 , j − 1 ] [i-1, j-1] [i−1,j−1] 的所有元素和。
2. 通过 d p dp dp 快速求子矩阵的和
   • 由于矩阵前缀和的下标与矩阵 m a t mat mat 并不是一一对应的，我们在计算子矩阵的起始位置与末尾位置的下标时要进行转换。
   • 根据题目可知，我们通过 i i i 和 j j j 求子矩阵的坐标时是可能会越界，我们要特殊处理。
   • s u m = d p [ x 2 ] [ y 2 ] − d p [ x 1 − 1 ] [ y 2 ] − d p [ x 2 ] [ y 1 − 1 ] + d p [ x 1 − 1 ] [ y 1 − 1 ] sum = dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1] sum=dp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]+dp[x1−1][y1−1]

代码实现

classSolution{public: vector<vector<int>>matrixBlockSum(vector<vector<int>>& mat,int k){//1.初始化前缀和数组，需要多加一行多加一列int m = mat.size(), n = mat[0].size();//dp[i][j]代表矩阵mat从[0][0]到[i-1][j-1]的所有元素的和 vector<vector<int>>dp(m +1,vector<int>(n +1));for(int i =1; i < m +1;++i)for(int j =1; j < n +1;++j) dp[i][j]= dp[i-1][j]+ dp[i][j-1]- dp[i-1][j-1]+ mat[i-1][j-1];//2.使用前缀和数组求和 vector<vector<int>>ret(m,vector<int>(n));for(int i =0; i < m;++i){//下标转换并且要进行越界情况的处理int x1 =max(0, i - k)+1;int x2 =min(m -1, i + k)+1;for(int j =0; j < n;++j){int y1 =max(0, j - k)+1;int y2 =min(n -1, j + k)+1; ret[i][j]= dp[x2][y2]- dp[x1-1][y2]- dp[x2][y1-1]+ dp[x1-1][y1-1];}}return ret;}};

代码解析：

1. 矩阵前缀和 d p dp dp 与矩阵 m a t mat mat 的下标不是一一对应的，比如 d p [ 1 ] [ 1 ] dp[1][1] dp[1][1] 对应原数组 m a t [ 0 ] [ 0 ] mat[0][0] mat[0][0] ，计算矩阵前缀和要留意。
2. 通过 i i i 与 j j j 求子矩阵的坐标时要防止越界并且转换成与 d p dp dp 数组对应，因为要通过 d p dp dp 求出子矩阵的所有元素和。

• 时间复杂度： O ( m × n ) O(m \times n) O(m×n)
• 空间复杂度： O ( m × n ) O(m \times n) O(m×n) ，矩阵前缀和数组 d p dp dp 的额外空间开销

Have a good day😏

See you next time, guys!😁✨🎞