题目描述

给出矩阵 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 的 1x1 子矩阵。

输入：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

算法

(枚举，哈希表) $O(n^3)$

1. 在矩阵中，对每行数字求前缀和。
2. 枚举左右边界 l 和 r，确定了左右边界后，我们可以将其化简一维数组的问题：即给定一个一维数组，求其中子数组为 target 的个数。
3. 一维的问题可以通过哈希表和前缀和解决：初始化哈希表 0 出现的次数为 1 次，遍历数组，每次求出当前位置的前缀和 tot，然后累计哈希表中 tot - target 出现的次数，最后 tot 的次数加 1。

时间复杂度

• 初始化前缀和的时间复杂度为 $O(n^2)$，枚举边界的时间为 $O(n^2)$，一维数组求解需要 $O(n)$ 的时间，故总时间复杂度为 $O(n^3)$。

空间复杂度

• 仅需要额外哈希表的空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        int ans = 0;

        for (int i = 0; i < n; i++)
            for (int j = 1; j < m; j++)
                matrix[i][j] += matrix[i][j - 1];

        for (int l = 0; l < m; l++)
            for (int r = l; r < m; r++) {
                unordered_map<int, int> vis;
                vis[0] = 1;
                int tot = 0;
                for (int k = 0; k < n; k++) {
                    if (l == 0) {
                        tot += matrix[k][r];
                    } else {
                        tot += matrix[k][r] - matrix[k][l - 1];
                    }
                    if (vis.find(tot - target) != vis.end())
                        ans += vis[tot - target];
                    vis[tot]++;
                }
            }
        return ans;
    }
};