力扣1074-元素和为目标值的子矩阵数量

  |  

摘要: 基于一维问题的解法,解决二维问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


$1 题目

1074. 元素和为目标值的子矩阵数量

给出矩阵 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’),那么这两个子矩阵也不同。

提示:

1
2
3
4
1 <= matrix.length <= 300
1 <= matrix[0].length <= 300
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8

示例 1:
输入:matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出:4
解释:四个只含 0 的 1x1 子矩阵。

示例 2:
输入:matrix = [[1,-1],[-1,1]], target = 0
输出:5
解释:两个 1x2 子矩阵,加上两个 2x1 子矩阵,再加上一个 2x2 子矩阵。

$2 题解

算法:前缀和 + HashMap

要求的是和为目标值的子矩阵数量,这个问题的一维版本是求和为目标值的子数组数量,这是个已经解决的问题,参考文章 在数据结构中维护前缀和

假设已经有了解决一维问题的接口,将二维的问题转化为一维的问题,然后调用接口解决,这是一种常见的思路,参考文章 二维转一维

1
int solve1d(const vector<int>& nums, const int target)

基于以上一维问题的接口,将二维问题转化为一维问题的算法如下:

1
2
3
4
5
预处理基于二维前缀和的子矩阵和的查询接口 sum_region(x1, y1, x2, y2)
枚举 i (0..n-1): O(N)
枚举 l : 0..i (子矩形的高的覆盖范围 [l..i]) O(N)
预处理出一维前缀和 sums[j] := sum_region(l, j, i, j) O(M)
在一维前缀和上求和为 K 的子数组有多少个 O(M)

总事件复杂度为 $O(N^{2}M)$。

代码 (C++)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
if(matrix.empty()) return 0;
int n = matrix.size();
int m = matrix[0].size();

sums2d = vector<vector<int> >(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
sums2d[i][j] = sums2d[i][j - 1] + sums2d[i - 1][j]
- sums2d[i - 1][j - 1] + matrix[i - 1][j - 1];

int ans = 0;
for(int i = 0; i < n; ++i)
for(int l = 0; l <= i; ++l)
{
vector<int> nums(m);
for(int j = 0; j < m; ++j)
nums[j] = sum_region(l, j, i, j);
ans += solve1d(nums, target);
}
return ans;
}

private:
vector<vector<int>> sums2d;
unordered_map<int, int> mapping;

int solve1d(const vector<int>& nums, const int target)
{
int m = nums.size();
mapping.clear();
mapping[0] = 1;
int sum = 0;
int ans = 0;
for(int j = 0; j < m; ++j)
{
sum += nums[j];
int gap = sum - target;
ans += mapping[gap];
++mapping[sum];
}
return ans;
}

int sum_region(int row1, int col1, int row2, int col2)
{
// row1 <= row2, col1 <= col2
return sums2d[row2 + 1][col2 + 1] - sums2d[row2 + 1][col1]
- sums2d[row1][col2 + 1] + sums2d[row1][col1];
}
};

Share