給出二維矩陣matrix，求其中滿足矩陣和等于target的子矩陣有幾個(gè)，O(n^4)暴力可過，計(jì)算矩陣的prefix sum再同時(shí)枚舉所有可能
1 #1074
2 #Runtime: 9219 ms (Beats 7.69%)
3 #Memory: 12.6 MB (Beats 100%)
4
5 class Solution(object):
6 def numSubmatrixSumTarget(self, matrix, target):
7 """
8 :type matrix: List[List[int]]
9 :type target: int
10 :rtype: int
11 """
12 ans = 0
13 n, m = len(matrix), len(matrix[0])
14 pre_sum = [[0] * (m + 1) for _ in xrange(n + 1)]
15 for i in xrange(1, n + 1):
16 for j in xrange(1, m + 1):
17 pre_sum[i][j] = pre_sum[i - 1][j] + pre_sum[i][j - 1] + matrix[i - 1][j - 1] - pre_sum[i - 1][j - 1]
18 for x in xrange(0, i):
19 for y in xrange(0, j):
20 if target == pre_sum[i][j] + pre_sum[x][y] - pre_sum[x][j] - pre_sum[i][y]:
21 ans += 1
22 return ans