写在文首

看了很多题解，大家大致的思路基本一致，时间复杂度为O(n·n·m)，但大多题解没有把过程表述的很完整，作为一个刷题的小白，我想在这写写小白也能看懂的思路，和做这道题的一些细节和收获

解题思路

题目要求既要考虑1x2, 2x1的情况, 也要考虑2x2的情况：
(1)先考虑1xn的情况，即在一行中(横向)可以找出多少个矩形**(这步我称之为"统计")**，代码如下：
统计行中的矩形数目 int now = 0; for (int k = 0; k < col; k++){ if (mat[j][k] == 0) now = 0; else now = k == 0 ? mat[j][0] : now + 1; ans += now; }

1. 当有连续三个1的时候，用now分别递增为1,2,3(第一个1可以形成一个矩形，第二个1和第一个1可以形成1个矩形加上其自身一共是两个，第三个1分别可以和前面连续的1形成两个长度分别为3,2的矩形，加上自身一共三个),并加到ans中
2. 这一步也可以记录连续的个数,使用等差数列求和公式计算连续1处可以形成的矩形数目，具体代码不展示
3. 当遍历到mat[j][k] == 0时，即1不连续了，置now为0，以便后面遇到连续1时进行统计

(2)压缩：

1. 理论上，纵向的矩形也可以像横向那样进行统计，但是我们注意到我们不仅要求横向和纵向的矩形，还要求诸如2x2之类的
2. 在(1)中我们得到所有大小为1的矩形和横向的各种大小的矩形的情况，所以后面我们只需要求纵向的大小大于1的矩形的情况即可
3. 所以在这我们选择向下"压缩"题目所给二维数组，以便继续统计，这里"压缩"的思路理解好下次遇到类似的题能想出来就行，来看图吧

起始的二维数组

对其使用“按位与”进行压缩

第二次统计的结果

思考：这里我们可以发现第二次的统计是2xn的，既包含了2X1的情况也包含了2x2的情况，接下来的步骤继续如上循环"压缩"即可

代码

###java

class Solution {
    public int numSubmat(int[][] mat) {
        int row = mat.length, col = mat[0].length, ans = 0;

        for (int i = 0; i < row; i++){
            //统计
            for (int j = i; j < row; j++){
                int now = 0;
                for (int k = 0; k < col; k++){
                    if (mat[j][k] == 0) now = 0;
                    else now = k == 0 ? mat[j][0] : now + 1;
                    ans += now;
                }
            }
            //压缩
            for (int j = row - 1; j > i; j--){
                for (int k = 0; k < col; k++){
                    mat[j][k] = mat[j][k] & mat[j - 1][k];
                }
            }
        }
        return ans;
    }
}

希望这篇题解能让你看懂，喜欢的留下你宝贵的会心一赞吧，刷题之路，我们绝不言败！ヾ(◍°∇°◍)ﾉﾞ