Leetcode 1074. 元素和为目标值的子矩阵数量
题目描述
给出矩阵 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’），那么这两个子矩阵也不同。
样例
输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1×1 子矩阵。
示例 2：
输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1×2 子矩阵，加上两个 2×1 子矩阵，再加上一个 2×2 子矩阵。
示例 3：
输入：matrix = [[904]], target = 0
输出：0
数据范围
1 <= matrix.length <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8
思路
二维前缀和+哈希
暴力的做法是预处理出二维前缀和后，然后便利每个子矩阵，在 n 和 m 同阶的情况下，复杂度是 O(n^4) 的。
事实上，我们能从「边」的角度来确定一个子矩阵，通过枚举三条边，然后加速找第四条边的过程，这样可以将复杂度降到 O(n^3)。
具体的，我们需要先预处理出一个二维前缀和。然后通过枚举确定「子矩阵的上下边界」，在将「子矩阵右边界」不断右移的过程中，把「子矩阵右边界」到「原矩阵左边界」行程的矩阵和存入哈希表（因为要统计数量，存储格式为 {“面积”:”出现次数”} ），然后通过容斥原理来找到目标的「子矩阵左边界」。
假设当前我们「子矩阵的上下边界」已经固定，当枚举到某个「子矩阵右边界」时，我们先通过二维前缀和计算出「子矩阵右边界」和「原矩阵左边界」形成的矩阵和 cur，由于我们希望找到矩阵和为 target 的子矩阵，即希望找到一个「子矩阵左边界」使得矩阵和满足要求，这等价于从「哈希表」中找到一个 x，使得 cur – x = target，这是一个 O(1) 操作。
代码
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int row = matrix.size(), col = matrix[0].size();
vector<vector<int>> prefix(row+1, vector<int>(col+1));
vector<vector<int>> dp(row+1, vector<int>(col+1));
// 预处理出前缀和
for(int i = 1; i<=row; i++)
for(int j = 1; j<=col; j++)
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1];
int ans = 0;
for (int top = 1; top <= row; top++) {
for (int bot = top; bot <= row; bot++) {
int cur = 0;
unordered_map<int, int> hashtable;
for (int r = 1; r <= col; r++) {
cur = prefix[bot][r] - prefix[top - 1][r];
if (cur == target) ans++;
if (hashtable.find(cur - target) != hashtable.end()) ans += hashtable[cur - target];
hashtable[cur]++;
}
}
}
return ans;
}
};
