题目分析

这个题目是一个困难题，问题描述比较简单，就是子矩阵之和等于target，求子矩阵的个数。思路很容易想到，但是能否找到一种时间复杂都最小的方法呢？

哈希表

看到这个题目，一开始并没有联想到Leetcode560题，而是直接使用二维数组前缀和来求解。首先计算二维数组curSum[i, j]，其中[i, j]代表从(0, 0)到(i, j)的所有元素之和。然后使用四重循环遍历矩阵的起始行，起始列，终止行和终止列，算法的时间复杂度为$O(n^2m^2)$，其中n和m分别代表行数和列数。

上述方法虽然可以得到正确结果，但是当n和m为1e2时，计算量达到1e8，这会TLE。因此无法正确提交，这时想到Leetcode560题，该题目是一维的问题，二维也可以类似求解。

遍历起始行i，在每个起始行中遍历终止行j，对于每一个终止行类似于一维问题，遍历终止列c，我们记录从[i, 0]到[j, c]之和sums，查看哈希表中sums - target的个数，然后将sums放入哈希表中。假如[i, 0]到[j, c1]之和为k1，从[i, 0]到[j, c2]之和为k1 + target，说明，从[i, c1 + 1]到[j, c2]的子矩阵是满足之和为target的。

算法只需要遍历起始行，终止行和终止列即可，且在循环时只需要用一维数组记录矩阵[i, 0]到[j, c]之和。**时间复杂度为$O(n^2m)$，空间复杂度为$O(m)$**。

下面是Python语言的题解

from collections import defaultdict


class Solution:
    def numSubmatrixSumTarget(self, matrix, target):
        row, col = len(matrix), len(matrix[0])
        res = 0
        for i in range(row):
            dp = [0] * (col + 1)
            for j in range(i, row):
                for c in range(col):
                    dp[c + 1] += matrix[j][c]
                dic = defaultdict(int)
                cur = 0
                for x in dp:
                    cur += x
                    res += dic[cur - target]
                    dic[cur] += 1
        return res

下面是Kotlin语言的题解

class Solution {
    fun numSubmatrixSumTarget(matrix: Array<IntArray>, target: Int): Int {
        val row = matrix.size
        val col = matrix[0].size
        var res = 0
        for (i in 0 until row) {
            val dp = IntArray(col + 1)
            for (j in i until row) {
                for (c in 0 until col) {
                    dp[c + 1] += matrix[j][c]
                }
                val dic = mutableMapOf<Int, Int>()
                var cur = 0
                for (x in dp) {
                    cur += x
                    res += dic[cur - target] ?: 0
                    dic[cur] = (dic[cur] ?: 0)  + 1
                }
            }
        }
        return res
    }
}

刷题总结

前缀和是经典的笔试面试题，因为这些年内卷的太严重了，导致算法题的难度逐渐增加，普通的前缀和已经不能满足要求了，需要小伙伴们多做一些难度较大的题目来扩展自己的视野。