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
| class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
matrix[i][j] += matrix[i][j - 1];
}
}
int ans = 0;
Map<Integer, Integer> sumCount = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
sumCount.clear();
int currSum = 0;
for (int k = 0; k < m; k++) {
currSum += matrix[k][j] - (i > 0 ? matrix[k][i - 1] : 0);
if (currSum == target) {
ans += 1;
}
int counterPart = currSum - target;
ans += sumCount.getOrDefault(counterPart, 0);
sumCount.put(currSum, sumCount.getOrDefault(currSum, 0) + 1);
}
}
}
return ans;
}
}
|
这道题可以简化为prefix sum. 思路就是把一些column叠起来. 比如让第0列和第1列叠起来, 此时我们在选任意一行, 比如第3行, 那么此时就构成了一个4 * 2的矩形. 这里叠起来的意思就是让重合的位置的值相加.
那么对于左上角在第0列的宽为2的矩形, 我们就可以让第0列和第1列叠起来, 然后像计算prefix sum那样从上到下遍历. 到一个地方记录此时的sum是多少, 然后看之前有没有是sum - k的sum.
有这个思路之后, 我们还有个问题就是比如说我想求左上角在第1列的矩形有哪些可以凑成k. 比如让第1列和第2列叠起来, 此时我们求左上角在第1列宽度为2的矩形有没有可以凑成k的. 此时我们要用到第1列 + 第二列的sum. 之前我们有用到第0列 + 第1列的sum. 于是我们可以先横向求prefix sum, 也就是每一个row的prefix sum先求出来. 然后当要遍历左上角在某个列的时候,j来表示此时的宽度, 我们就能快速得出i和j之间的sum是多少. 也就是i到j之间列叠起来后的sum是多少(就是0到j处的sum - 0到i处的sum).
感觉这道题话语很难描述清楚.
时间复杂度: O(m * n *n)
空间复杂度: O(m) 就是那个hashmap存叠起来后压成的array的prefix sum
