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
38
39
40
|
# 1074. Number of Submatrices That Sum to Target
from collections import defaultdict
"""
given a 'matrix' and '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 are
different if they have some coordinate that is different. for example if x1
!= x1
"""
class Solution(object):
def numSubmatrixSumTarget(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: int
"""
m, n = len(matrix), len(matrix[0])
for row in matrix:
for i in range(n - 1):
row[i + 1] += row[i]
ans = 0
for i in range(n):
for j in range(i, n):
c = collections.defaultdict(int)
curr, c[0] = 0, 1
for k in range(m):
curr += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)
ans += c[curr - target]
c[curr] += 1
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.numSubmatrixSumTarget(matrix=[[0, 1, 0], [1, 1, 1], [0, 1, 0]], target=0))
print(obj.numSubmatrixSumTarget(matrix=[[1, -1], [-1, 1]], target=0))
print(obj.numSubmatrixSumTarget(matrix=[[904]], target=0))
|