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

叁歲伎倆 2022-10-16 09:50 46阅读 0赞

给出矩阵 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\] <= 1000  
\-10^8 <= target <= 10^8

class Solution {
    public:
        int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
            int n = matrix.size(),m=matrix[0].size();
            // vector<vector<int>> a(n+1,vector<int>(m+1));   巨消耗时间的代码
            int a[101][101];
            for(int i =1;i<=n;i++)
            {
                for(int j = 1;j<=m;j++)
                {
                    a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+matrix[i-1][j-1];
                }
            }
            int ret = 0;
            for(int i = 1;i<=n;i++)
            for(int j = 1;j<=m;j++)
            for(int i1 = i;i1<=n;i1++)
            for(int j1=j;j1<=m;j1++)
            {
                if(a[i1][j1]-a[i1][j-1]-a[i-1][j1]+a[i-1][j-1]==target) ret++;
            }
            return ret;
        }
    };

![20210529141511410.png][]

class Solution {
    public:
        int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
            int n = matrix.size(),m=matrix[0].size();
            int ret = 0;
            for(int i = 0;i<n;++i)
            {
                int sum[101]={0};
                for(int i1 = i;i1<n;i1++)
                {
                    for(int j = 0;j<m;j++)
                    {
                        sum[j] += matrix[i1][j];
                    }
                    unordered_map<int,int> mp;
                    mp[0]=1;
                    int s = 0;
                    for(int j = 0;j<m;j++)
                    {
                        s+=sum[j];
                        ret+=mp[s-target];
                        mp[s]++;
                    }
                }
            }
            return ret;
        }
    };

![20210529143253939.png][]

从时间复杂度是上分析，方法二的时间复杂度是比较低的，也可能是数据的问题吧,而且方法二重新声明的变量的次数较多。

方法一时间复杂度O(n\*n\*n\*m\*m),方法二时间复杂度O(n\*n\*m\*log(m))

[20210529141511410.png]: /images/20221014/7dae030ca468474a85210f849bb81847.png
[20210529143253939.png]: /images/20221014/cbc813f834204e0f8c72a682e8702270.png