C++刷leetcode（1074. 元素和为目标值的子矩阵数量）【前缀和】
题目描述：给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix 的集合。
如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。
示例 1：
输入：matrix = [,,], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。
示例 2：
输入：matrix = [,[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
示例 3：
输入：matrix = [], target = 0
输出：0
提示：
1 <= matrix.length <= 100
1 <= matrix.length <= 100
-1000 <= matrix <= 1000
-10^8 <= target <= 10^8
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-submatrices-that-sum-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int res = 0;
//前缀和
int len1 = matrix.size(), len2 = matrix.size();
vector<vector<int> >sum(len1, vector<int>(len2, 0));
//初始化
sum = matrix;
for(int j = 1; j < len2; j++){
sum = sum + matrix;
}
for(int i = 1; i < len1; i++){
sum = sum + matrix;
}
//动态规划
for(int i = 1; i < len1; i++){
for(int j = 1; j < len2; j++){
sum = sum + sum - sum + matrix;
}
}
for(int x1 = 0; x1 < len1; x1++){
for(int x2 = x1; x2 < len1; x2++){
for(int y1 = 0; y1 < len2; y1++){
for(int y2 = y1; y2 < len2; y2++){
int temp = 0;
if(x1 == 0 && y1 == 0){
temp = sum;
}else if(x1 == 0){
temp = sum - sum;
}else if(y1 == 0){
temp = sum - sum;
}else{
temp = sum - sum - sum + sum;
}
if(temp == target){
res++;
}
}
}
}
}
return res;
}
};
前缀和参考视频：https://www.bilibili.com/video/BV1pi4y1j7si?spm_id_from=333.337.search-card.all.click 相同思路的简便算法
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int res = 0;
//前缀和
int len1 = matrix.size(), len2 = matrix.size();
vector<vector<int> >sum(len1+1, vector<int>(len2+1, 0));
//动态规划
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; j++){
sum = sum + sum - sum + matrix;
}
}
for(int x1 = 1; x1 <= len1; x1++){
for(int x2 = x1; x2 <= len1; x2++){
for(int y1 = 1; y1 <= len2; y1++){
for(int y2 = y1; y2 <= len2; y2++){
int temp = sum - sum - sum + sum;
if(temp == target){
res++;
}
}
}
}
}
return res;
}
};
页:
[1]