算法1

前缀和 加字典(sliding window)

时间复杂度 $O(n^3)$

python3 代码

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        r, c = len(matrix), len(matrix[0])
        ans = 0
        for rr in matrix:
            for j in range(1,c):
                rr[j] += rr[j-1]
        for i in range(0,c):
            for j in range(i,c):
                d = collections.defaultdict(int)
                tmp = 0
                d[0] = 1
                for k in range(r):
                    tmp += matrix[k][j] - (matrix[k][i-1] if i > 0 else 0)
                    ans += d[tmp-target]
                    d[tmp] += 1
        return ans