元素和为目标值的子矩阵数量

难度: Hard

给出矩阵 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 <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i][j] <= 1000
-10^8 <= target <= 10^8

Submission

运行时间: 331 ms

内存: 16.9 MB

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        res = 0
        for top in range(m):
            rowPrefix = [0] * n
            for bottom in range(top, m):
                colPrefix = 0
                colPrefix_dict = {0:1}
                for col in range(n):
                    rowPrefix[col] += matrix[bottom][col]
                    colPrefix += rowPrefix[col]
                    tmp = colPrefix - target
                    if tmp in colPrefix_dict:
                        res += colPrefix_dict[tmp]
                    if colPrefix in colPrefix_dict:
                        colPrefix_dict[colPrefix] += 1
                    else:
                        colPrefix_dict[colPrefix] = 1
        return res

Explain

此题解采用了前缀和与哈希表的方法来计算子矩阵的和。首先，固定子矩阵的上边界top和下边界bottom，对于每个可能的上下边界对，计算从第0列到当前列的子矩阵的和。通过维护一个行前缀和数组rowPrefix来记录当前列的累加和。然后，使用一个哈希表colPrefix_dict来存储所有可能的列前缀和的出现次数，从而快速检查当前列前缀和减去目标值target是否已经出现过，以判断是否存在符合条件的子矩阵。这种方法避免了直接计算每个子矩阵的和，从而提高了效率。

时间复杂度: O(m^2 * n)

空间复杂度: O(n)

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])  # 矩阵的行数和列数
        res = 0  # 用于计数符合条件的子矩阵数量
        for top in range(m):  # 上边界
            rowPrefix = [0] * n  # 初始化行前缀和数组
            for bottom in range(top, m):  # 下边界
                colPrefix = 0  # 列前缀和
                colPrefix_dict = {0: 1}  # 哈希表，用于存储列前缀和的出现次数，初始化为{0: 1}表示空矩阵的情况
                for col in range(n):  # 遍历每一列
                    rowPrefix[col] += matrix[bottom][col]  # 更新行前缀和
                    colPrefix += rowPrefix[col]  # 更新列前缀和
                    tmp = colPrefix - target  # 计算当前列前缀和与目标值的差
                    if tmp in colPrefix_dict:  # 如果差值在哈希表中，说明存在符合条件的子矩阵
                        res += colPrefix_dict[tmp]  # 累加找到的子矩阵数量
                    if colPrefix in colPrefix_dict:  # 更新哈希表
                        colPrefix_dict[colPrefix] += 1
                    else:
                        colPrefix_dict[colPrefix] = 1
        return res

Explore

前缀和与哈希表的组合在处理子数组或子矩阵的和问题中效果良好，原因在于这种方法能够有效减少重复计算并快速查询。具体来说，前缀和可以用来计算任何子数组或子矩阵的和，通过存储累加值，可以在O(1)时间内得到任意区间的和。而哈希表的使用则允许我们在O(1)的时间复杂度内查找之前出现过的前缀和，这对于快速检查当前前缀和与目标值的差值是否已存在至关重要。在本题中，我们利用哈希表记录所有可能的列前缀和的出现次数，当遍历到新的列时，可以立即判断以当前列为右边界的、符合目标和的子矩阵的数量。这种方法显著提高了效率，尤其是在处理大数据量时。

在使用哈希表记录前缀和的时候，初始化为`{0: 1}`是为了处理那些从矩阵的起始位置开始且和恰好为目标值的子矩阵。这个初始化意味着存在一个虚拟的前缀和为0，这有助于处理当整个子矩阵（从起始累积到当前位置）的和刚好等于目标值的情况。例如，如果当前的列前缀和正好等于目标值，那么根据前缀和的性质，当前列前缀和减去0（即前缀和本身）会留下一个满足条件的子矩阵，因此我们可以通过检查哈希表来直接统计这类情况的子矩阵数量。

在计算子矩阵的和时，我们需要考虑各种不同的上边界和下边界的组合，这意味着每一对上下边界定义了一个新的子矩阵范围。为了正确计算每个这样的子矩阵的和，我们需要从当前的上边界top到下边界bottom逐行累加，从而更新行前缀和数组。如果直接计算整个矩阵的行前缀和，我们将无法得到仅限于特定上下边界之间的行的累计和，这是因为不同的上下边界对定义了不同的子矩阵。因此，为了保证精确计算每个可能的子矩阵的和，我们需要根据当前考虑的上下边界动态计算行前缀和。