程序从矩阵中找出子矩阵的数量，其中元素的总和等于 C++ 中的特定值
假设我们有一个包含整数值的矩阵。我们必须从矩阵中找出子矩阵，其中矩阵元素的总和等于给定的目标总和值。我们返回子矩阵的数量。
所以，如果输入是这样的
并且目标=5，那么输出将为3。
元素和等于6的子矩阵的数量是2。
示例
让我们看看以下实现以获得更好的理解-
#include<bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>>& mat, int sumTarget) {
int n = mat.size();
int m = n == 0 ? 0 : mat[0].size();
if (m > n) {
vector<vector<int>> transpose(m, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
transpose[j][i] = mat[i][j];
}
}
return solve(transpose, sumTarget);
}
int ans = 0;
for (int p = 0; p < m; p++) {
vector<int> arr(n);
for (int q = p; q < m; q++) {
for (int i = 0; i < n; i++) {
arr[i] += mat[i][q];
}
unordered_map<int, int> pcnt = {{0, 1}};
int pref = 0;
for (int i = 0; i < n; i++) {
pref += arr[i];
auto tmp = pcnt.find(pref - sumTarget);
if (tmp != end(pcnt)) ans += tmp->second;
pcnt[pref]++;
}
}
}
return ans;
}
int main() {
vector<vector<int>> mat = {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}};
cout<< solve(mat, 5) <<endl;
return 0;
}输入
{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}, 5输出结果3