算法leetcode

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

字数统计: 819字   |   阅读时长: 3分
, ,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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