力扣1074.元素和为目标值的子矩阵数量

力扣1074.元素和为目标值的子矩阵数量

• 前缀和 + 哈希表

  • 见力扣363.
  • 枚举上下边界转化一维前缀和，用哈希表储存出现次数

•   class Solution {public:int numSubmatrixSumTarget(vector<vector<int>>& matrix, int k) {int ans = 0;int m = matrix.size(),n = matrix[0].size();for(int i=0;i<m;i++){vector<int> sum(n);for(int j=i;j<m;j++){for(int c=0;c<n;c++)sum[c] += matrix[j][c];unordered_map<int,int> sumset;sumset[0] = 1;int s = 0;for(int v:sum){s += v;if(sumset.find(s-k) != sumset.end())ans += sumset[s-k];sumset[s] ++;}}}return ans;}};