C ++中要求和的子矩阵数
假设我们有一个矩阵和一个目标值，我们必须找到总和与目标相同的非空子矩阵的数量。这里，子矩阵[(x1,y1)，(x2,y2)]是所有单元矩阵的集合[x][y]，其中x的范围为x1和x2，y的范围为y1和y2。如果两个子矩阵的坐标不同，则两个子矩阵[[x1，y1），(x2,y2)]和[[x1'，y1'），（x2'，y2'）]不同。与x1'相同。
所以，如果输入像
并且target=0，则输出将为4，这是因为四个仅包含0的1x1子矩阵。
为了解决这个问题，我们将遵循以下步骤-
回答：=0
col：=列数
行：=行数
对于初始化i：=0，当i<行，更新（将i增加1）时，执行-
矩阵[i，j]：=矩阵[i，j]+矩阵[i，j-1]
对于初始化j：=1，当j<col时，更新（将j增加1），做-
定义一张映射
对于初始化i：=0，当i<col时，更新（将i增加1），执行-
当前：=矩阵[k，j]
如果i-1>=0，则-
总和：=总和+当前
ans：=ans+m[target-sum]
m[-sum]增加1
当前：=当前-矩阵[k，i-1]
清除映射m
m[0]：=1
和：=0
对于初始化j：=i，当j<col时，更新（将j增加1），-
对于初始化k：=0，当k<行时，更新（将k增加1），执行-
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int
target) {
int ans = 0;
int col = matrix[0].size();
int row = matrix.size();
for(int i = 0; i < row; i++){
for(int j = 1; j < col; j++){
matrix[i][j] += matrix[i][j - 1];
}
}
unordered_map <int, int> m;
for(int i = 0; i < col; i++){
for(int j = i; j < col; j++){
m.clear();
m[0] = 1;
int sum = 0;
for(int k = 0; k < row; k++){
int current = matrix[k][j];
if(i - 1 >= 0)current -= matrix[k][i - 1];
sum += current;
ans += m[target - sum];
m[-sum]++;
}
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
cout << (ob.numSubmatrixSumTarget(v, 0));
}输入值
{{0,1,0},{1,1,1},{0,1,0}}, 0输出结果
4