题目
给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
如果 (x1, y1, x2, y2) 和 (x1‘, y1‘, x2‘, y2‘) 两个子矩阵中部分坐标不同（如：x1 != x1‘），那么这两个子矩阵也不同。
示例 1：
输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。
示例 2：
输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
提示：
1 <= matrix.length <= 300
1 <= matrix[0].length <= 300
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8
解题思路
这边matrix.length是300，所以空间复杂度最好控制在O(n^2)。最容易想到的是O(n^4)复杂度的算法。
从以上出发，可以考虑求和的特殊性，把复杂度降低到O(n^3)。
这道题的难点在于二维dp要非常注意顺序，但是如果直接考虑最普遍的矩阵 (x1, y1, x2, y2) 容易不知道从何下手。但是如果从O(n^4)的算法出发，就能发现怎么做简化了。
可以看出，矩形可以被分为，用两个参数表示的，用三个参数表示的和用四个参数表示的。三个参数的矩形可以从两个参数的矩形推出（相减），四个参数的矩形可以从三个参数的矩形推出（相减）。如果单纯发现了相减的关系，可以得到O(n^4)的算法。
当我们考虑到四个参数的矩形是由三个参数的矩形得到的时候，可以根据和为sum-target的矩形的个数，去掉对第四个参数的枚举。要得到个数，考虑到和可能很大，所以用unordered_map<int, int>（哈希）。
代码
class Solution {
public:
int dp[310][310];
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int n=matrix.size(),m=matrix[0].size();
int pre=0;
for(int i=0;i<n;i++){
pre=0;
for(int j=0;j<m;j++){
pre+=matrix[i][j];
if(i==0)dp[i][j]=pre;
else dp[i][j]=dp[i-1][j]+pre;
}
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
unordered_map<int,int>mp;
for(int k=0;k<m;k++){
int num=0;
if(i==0)num=dp[j][k];
else num=dp[j][k]-dp[i-1][k];
if(num==target)ans++;
if(mp.find(num-target)!=mp.end())ans+=mp[num-target];
mp[num]++;
}
}
}
return ans;
}
};
https://blog.csdn.net/qq_37466069/article/details/94172704
https://blog.csdn.net/mathjohn/article/details/92433298
原文：https://www.cnblogs.com/ljy08163268/p/11679552.html