一、题目
给出矩阵 matrix 和目标值 target,返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐标不同(如:x1 != x1’),那么这两个子矩阵也不同。
二、思路
sum(matrix[0][0],matris[i][j])指从从matrix左上角(0, 0)到右下角(i, j)区块中所有元素的和。
1)二维数组前缀和
建立dp数组,dp[i+1][j+1]代表了sum(matrix[0][0],matris[i][j])区块的和。根据前缀和可以快速得到某一区块的值:
s
u
m
(
m
a
t
r
i
x
[
a
]
[
b
]
,
m
a
t
r
i
s
[
i
]
[
j
]
)
=
d
p
[
i
+
1
]
[
j
+
1
]
−
d
p
[
a
]
[
j
+
1
]
−
d
p
[
i
+
1
]
[
b
]
+
d
p
[
a
]
[
b
]
sum(matrix[a][b],matris[i][j])=dp[i+1][j+1]-dp[a][j+1]-dp[i+1][b]+dp[a][b]
sum(matrix[a][b],matris[i][j])=dp[i+1][j+1]−dp[a][j+1]−dp[i+1][b]+dp[a][b]
通过遍历数组,以各个元素为起点,不同区块大小进行遍历,构成四重循环进行求解。
2)前缀和+哈希表
先确定上边界up和下边界down,将每个sum(matrix[up][0],matris[down-1][k])放入哈希表map中,其中k为[0, matrix[0].length):
s
u
m
(
m
a
t
r
i
x
[
u
p
]
[
0
]
,
m
a
t
r
i
s
[
d
o
w
n
−
1
]
[
k
]
)
=
d
p
[
d
o
w
n
]
[
c
o
l
+
1
]
−
d
p
[
u
p
]
[
c
o
l
+
1
]
sum(matrix[up][0],matris[down-1][k])=dp[down][col + 1] - dp[up][col+1]
sum(matrix[up][0],matris[down−1][k])=dp[down][col+1]−dp[up][col+1]
故而,只需要寻找map中sum(matrix[up][0],matris[down-1][k])-target值的个数,节省了遍历时间。
三、代码
1)二维数组前缀和
class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
for (int i = 0; i < matrix.length; i++) { // 前缀求和
for (int j = 0; j < matrix[0].length; j++) {
dp[i+1][j+1] = matrix[i][j] + dp[i+1][j] + dp[i][j+1] - dp[i][j];
}
}
int ans = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) { // i,j是确定以matrix[i][j]为左上角起点
for (int high = 1; high <= matrix.length - i; high++) { // high、width分别为区块的高度和宽度
for (int width = 1; width <= matrix[0].length - j; width++) {
if (dp[i+high][j+width] - dp[i][j+width] - dp[i+high][j] + dp[i][j] == target) {
ans++;
}
}
}
}
}
return ans;
}
}
matrix行和列数分别为m、n,时间复杂度为O(mn),空间复杂度为O(mn)。
2)前缀和+哈希表
class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
dp[i+1][j+1] = matrix[i][j] + dp[i+1][j] + dp[i][j+1] - dp[i][j];
}
}
int ans = 0;
for (int up = 0; up < matrix.length; up++) {
for (int down = up+1; down <= matrix.length; down++) {
Map<Integer, Integer> map = new HashMap();
for (int col = 0; col < matrix[0].length; col++) {
int val = dp[down][col + 1] - dp[up][col+1];
if (val == target) {
ans++;
}
ans += map.getOrDefault(val - target, 0);
map.put(val, map.getOrDefault(val, 0) + 1);
}
}
}
return ans;
}
}
matrix行和列数分别为m、n,时间复杂度为O(mn),空间复杂度为O(mn)。