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

样例


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

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

输入:matrix = [[904]], target = 0
输出:0

数据范围

1 <= matrix.length <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8

思路

二维前缀和+哈希
暴力的做法是预处理出二维前缀和后,然后便利每个子矩阵,在 nm 同阶的情况下,复杂度是 O(n^4) 的。

事实上,我们能从「边」的角度来确定一个子矩阵,通过枚举三条边,然后加速找第四条边的过程,这样可以将复杂度降到 O(n^3)

具体的,我们需要先预处理出一个二维前缀和。然后通过枚举确定「子矩阵的上下边界」,在将「子矩阵右边界」不断右移的过程中,把「子矩阵右边界」到「原矩阵左边界」行程的矩阵和存入哈希表(因为要统计数量,存储格式为 {“面积”:”出现次数”} ),然后通过容斥原理来找到目标的「子矩阵左边界」。

假设当前我们「子矩阵的上下边界」已经固定,当枚举到某个「子矩阵右边界」时,我们先通过二维前缀和计算出「子矩阵右边界」和「原矩阵左边界」形成的矩阵和 cur,由于我们希望找到矩阵和为 target 的子矩阵,即希望找到一个「子矩阵左边界」使得矩阵和满足要求,这等价于从「哈希表」中找到一个 x,使得 cur – x = target,这是一个 O(1) 操作。

代码

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int row = matrix.size(), col = matrix[0].size();
        vector<vector<int>> prefix(row+1, vector<int>(col+1));
        vector<vector<int>> dp(row+1, vector<int>(col+1));
        // 预处理出前缀和
        for(int i = 1; i<=row; i++)
            for(int j = 1; j<=col; j++)
                prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1];
        int ans = 0;
        for (int top = 1; top <= row; top++) {
            for (int bot = top; bot <= row; bot++) {
                int cur = 0;
                unordered_map<int, int> hashtable;
                for (int r = 1; r <= col; r++) {
                    cur = prefix[bot][r] - prefix[top - 1][r];
                    if (cur == target) ans++;
                    if (hashtable.find(cur - target) != hashtable.end()) ans += hashtable[cur - target];
                    hashtable[cur]++;
                }
            }
        }
        return ans;
    }
};

发表回复

您的电子邮箱地址不会被公开。