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'），那么这两个子矩阵也不同。
示例 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 子矩阵。
示例 3：
输入：matrix = [[904]], target = 0
输出：0
提示：
1 <= matrix.length <= 1001 <= matrix[0].length <= 100-1000 <= matrix[i] <= 1000-10^8 <= target <= 10^8
数组 困难 动态规划
题解
事实上，我们能从「边」的角度来确定一个子矩阵，通过枚举三条边，然后加速找第四条边的过程，这样可以将复杂度降到 $O(n3)$。
这个分析思路在 （题解）363. 矩形区域不超过 K 的最大数值和 详细讲过，没有印象的同学可以翻翻。这道题一定程度上是那道题的简化版，在本题我们只需要找到矩阵和为 target 的值，因此只需要使用「哈希表」来记录出现过的值即可，而在 （原题）363. 矩形区域不超过 K 的最大数值和 中，我们需要找到和不超过 k 的最大子矩阵，因此还涉及「有序集合 + 二分」。
具体的，我们仍然需要先预处理出一个二维前缀和。然后通过枚举确定「子矩阵的上下边界」，在将「子矩阵右边界」不断右移的过程中，把「子矩阵右边界」到「原矩阵左边界」行程的矩阵和存入哈希表（因为要统计数量，存储格式为 {"面积”:"出现次数"} ），然后通过容斥原理来找到目标的「子矩阵左边界」。
假设当前我们「子矩阵的上下边界」已经固定，当枚举到某个「子矩阵右边界」时，我们先通过二维前缀和计算出「子矩阵右边界」和「原矩阵左边界」形成的矩阵和 cur，由于我们希望找到矩阵和为 target 的子矩阵，即希望找到一个「子矩阵左边界」使得矩阵和满足要求，这等价于从「哈希表」中找到一个 x，使得 cur - x = target，这是一个 $O(1)$ 操作。
代码
class Solution:
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
m, n = len(matrix), len(matrix[0])
ans = 0
for i in range(1, n + 1):
presum = [0] * (m + 1)
for j in range(i, n + 1):
a = 0
d = {0:1}
for fixed in range(1, m + 1):
presum[fixed] += matrix[fixed-1][j-1]
a += presum[fixed]
if a - target in d:
ans += d[a - target]
if a in d:
d[a] += 1
else:
d[a] = 1
return ans
Python暴力搜索会超时，卡在38例：38 / 40 个通过测试用例
class Solution:
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
m, n = len(matrix), len(matrix[0])
cum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1,m+1):
for j in range(1,n+1):
cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + matrix[i-1][j-1]
ans = 0
for x1 in range(1,m+1):
for y1 in range(1,n+1):
for x2 in range(x1,m+1):
for y2 in range(y1,n+1):
cur = cum[x2][y2] - cum[x1-1][y2] - cum[x2][y1-1] + cum[x1-1][y1-1]
if cur == target:
ans += 1
return ans