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

矩阵前缀和。因为矩阵中可能包含负值，所以这题肯定不会存在什么剪枝，动态规划的可能性。所以这个题也就没什么弯弯绕绕。个人感觉算不上个Hard题目。

最直观的思路就是枚举子矩阵，既枚举矩阵的左上角节点和右下角节点所构成的子矩阵。枚举是4层循环。

然后矩阵和的计算是两层循环，肯定不能套在枚举子矩阵的循环里。

我们维护一个矩阵前缀和，即prefix[p][q]是左上角0，0节点和右下角p，q节点构成矩阵的面积和。

那么对于任意矩阵:(i,j)(p,q)，其矩阵和 = prefix[p][q] – prefix[i-1][q] – prefix[p][j-1] + prefix[i-1][j-1]

可以在纸上画一下图，一下子就能看明白了。

最终的时间复杂度为O(n^4)

class Solution {

    public int numSubmatrixSumTarget(int[][] matrix, int target) {

        int m = matrix.length;

        if (m == 0) {

            return 0;

        }

        int n = matrix[0].length;

        int[][] f = new int[m][n];

        for (int i = 0; i<m ;i++) {

            f[i][0] = matrix[i][0];

            for (int j = 1; j<n ; j++) {

                f[i][j] = f[i][j-1] + matrix[i][j];

            }

        }

        // 左上角为0，0；右下角为i,j

        int[][] prefixSum = new int[m][n];

        for (int i=0;i<m;i++) {

            for (int j=0;j<n;j++) {

                if (i>0) {

                    prefixSum[i][j] = prefixSum[i-1][j];

                }

                prefixSum[i][j] += f[i][j];

            }

        }

        int ans = 0;

        for (int i=0;i<m;i++) {

            for (int j=0;j<n;j++) {

                for (int p = i;p<m;p++) {

                    for (int q=j;q<n;q++) {

                        int sum = prefixSum[p][q];

                        if (i>0) {

                            sum -= prefixSum[i-1][q];

                        }

                        if (j>0) {

                            sum -= prefixSum[p][j-1];

                        }

                        if (i>0&&j>0) {

                            sum += prefixSum[i-1][j-1];

                        }

                        if (sum == target) ans++;

                    }

                }

            }

        }

        return ans;

    }

}

巴特西

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

最新文章

热门文章