LeetCode 1074. Number of Submatrices That Sum to Target

偏执的太偏执、 2023-07-12 03:55 36阅读 0赞

### 这个题目如果跟着单调栈的题目后边写会很有感觉，单调栈的典型题目可以参考： ###

[https://blog.csdn.net/qq\_41685265/article/details/104241825][https_blog.csdn.net_qq_41685265_article_details_104241825]

## 题目描述 ##

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

## 算法 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70][]

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;
        }
    };

[https_blog.csdn.net_qq_41685265_article_details_104241825]: https://blog.csdn.net/qq_41685265/article/details/104241825
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306232237414.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70