统计全1子矩形Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个子矩形的元素全部都是 1 。

示例 1：

输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

提示：

1 <= m, n <= 150
mat[i][j] 仅包含 0 或 1

# 思路

二维数组前缀和

# 解法


class Solution {
public int numSubmat(int[][] mat) {
    int m = mat.length;
    int n = mat[0].length;
    int[][] prefixSum = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + mat[i - 1][j - 1];
        }
    }

    int count = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int x = i; x <= m; x++) {
                for (int y = j; y <= n; y++) {
                    int sum = prefixSum[x][y] + prefixSum[i - 1][j - 1] - prefixSum[i - 1][y] - prefixSum[x][j - 1];
                    if (sum == (x - i + 1) * (y - j + 1)) {
                        count++;
                    }
                }
            }
        }
    }
    return count;
}
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java