1074. Number of Submatrices That Sum to Target
Given a matrix and a target, return the number of non-empty submatrices that sum to target.
A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.
Two submatrices (x1, y1, x2, y2) and (x1’, y1’, x2’, y2’) are different if they have some coordinate that is different: for example, if x1 != x1’.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int res = 0, n = matrix.size(), m = matrix[0].size();
for(int i = 0; i < n; i++)
for(int j = 1; j < m; j++)
matrix[i][j] += matrix[i][j-1];
unordered_map<int, int> mp;
for(int i = 0; i < m; i++)
for(int j = i; j < m; j++) {
mp = {{0, 1}};
int sum = 0;
for(int k = 0; k < n; k++) {
sum += matrix[k][j] - (i ? matrix[k][i - 1] : 0);
res += mp[sum - target];
mp[sum]++;
}
}
return res;
}
};
|
