题目
https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/
给定一个m * n的矩阵,求有多少个子矩阵,满足其中元素的和等于target。m, n <= 300。
做法
经典题。首先区间求和一定要用前缀和。枚举子矩阵的左右边界[l, r],那么我们只需要处理[l, r]中间的这一块。这部分的前缀和可以预处理出来。然后用一个hash map统计即可。如果hash map是O(1)的,那么算法时间复杂度为O($n^3$)。
1 | class Solution { |