leetcode 1074 - Number of Submatrices That Sum to Target

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = matrix[0].size();
int total = 0;

for (int r = 0; r < row; r++) {
vector<int> row_sum(col, 0);

for (int i = r; i < row; i++) {
for (int j = 0; j < col; j++)
row_sum[j] += matrix[i][j];
total += numResult(row_sum, target);
}
}

return total;
}

int numResult(vector<int> &row_sum, int target) {
unordered_map<int, int> map;
int s = 0;
int total = 0;

map[0] = 1;

for (int n : row_sum) {
s += n;

total += map[s - target];
map[s]++;
}

return total;
}
};