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

提示：

1 <= matrix.length <= 3001 <= matrix[0].length <= 300-1000 <= matrix[i] <= 1000-10^8 <= target <= 10^8

题解

已知该矩阵大小为(h, w)，首先用数组matrix[x1][y1]记录从(0, 0)点到(x1, y1)内所有元素的和，枚举所有连续行(x1, x2)(其中 0<x1<=x2<h)，然后从左向右遍历列。
每遍历到一列y就将这一段横坐标范围(x1, x2)纵坐标范围(0, y)区间内的所有元素和S加入unordered_map中，并在unordered_map中寻找 S-target，若存在，则说明在y的前面存在y0 < y，使得横坐标范围(x1, x2)纵坐标范围(y0, y)内的所有元素和为target。

代码

C

class Solution {public:    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {        int n = matrix.size();        int m = matrix[0].size();        int ans = 0;        for(int i = 0; i < n; i  )        {            for(int j = 0; j < m; j  )            {                if(i)                {                    matrix[i][j]  = matrix[i - 1][j];                }                if(j)                {                    matrix[i][j]  = matrix[i][j - 1];                }                if(i && j)                {                    matrix[i][j] -= matrix[i - 1][j - 1];                }            }        }        for(int i = 0; i < n; i  )        {            for(int j = i; j < n; j  )            {                unordered_map<int, int> bag;                bag[0] = 1;                for(int k = 0; k < m; k  )                {                    int current = matrix[j][k] - (i == 0 ? 0 : matrix[i - 1][k]);                    unordered_map<int, int>::iterator it = bag.find(current-target);                    if(it != bag.end())                    {                        ans  = it->second;                    }                    it = bag.find(current);                    if(it != bag.end())                    {                        it->second  ;                    }                    else{                        bag.insert({current, 1});                    }                }            }        }        return ans;    }};

来源：https://www.icode9.com/content-4-280101.html