目标值子矩阵的数量

问题描述
小M最近在研究矩阵，他对矩阵中的子矩阵很感兴趣。给定一个矩阵 matrix 和一个目标值 target，他的任务是找到所有总和等于目标值的非空子矩阵的数量。子矩阵通过选择矩阵的某个矩形区域定义，形式为 (x1, y1, x2, y2)，其中 (x1, y1) 表示左上角的坐标，(x2, y2) 表示右下角的坐标。一个子矩阵包含矩阵中所有位于这个矩形区域内的单元格。如果两个子矩阵的坐标不同（如 x1 != x1’ 或 y1 != y1’），则这两个子矩阵被认为是不同的。
你需要返回满足条件的子矩阵数量。

测试样例

样例1：

输入：matrix = [[-1,1,0], [1,1,1], [0,1,0]] ,target = 0
输出：7

样例2：

输入：matrix = [[-1,-1], [-1,1]] ,target = 0
输出：2

样例3：

输入：matrix = [[-1,2,3], [4,5,6], [7,8,9]] ,target = 10
输出：2

题解

二维前缀和，枚举左上角的点和右下角的点。时间复杂度O(n^2 * m^2)

#include <iostream>
#include <vector>
using namespace std;int solution(vector<vector<int>>& matrix, int target) {// PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE// write code hereint n = matrix.size();int m = matrix[0].size();vector<vector<int>> ans(n+1, vector<int>(m+1, 0));int res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ans[i+1][j+1] = matrix[i][j] + ans[i][j+1] + ans[i+1][j] - ans[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int r = i ; r < n; r++) {for (int c = j ; c < m; c++) {int tmp = ans[r+1][c+1] - ans[r+1][j] - ans[i][c+1] + ans[i][j];if (target == tmp) {res++;}}}}}return res;
}

优化枚举左上点和右下点的枚举。使用前缀和+ 哈希表进行优化。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;int solution(vector<vector<int>>& matrix, int target) {// PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE// write code hereint n = matrix.size();int m = matrix[0].size();vector<vector<int>> ans(n+1, vector<int>(m+1, 0));int res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ans[i+1][j+1] = matrix[i][j] + ans[i][j+1] + ans[i+1][j] - ans[i][j];}} // top代表左上点的行号for (int top = 0; top< n; top++) {// bottom 代表右下点的行号for (int bottom = top; bottom < n; bottom ++) {// 存储前缀和的数量unordered_map<int, int> sumCount;sumCount[0] = 1;for (int col = 0; col < m; col++) {// 这里计算出来的就是[top][col] - [bottom][col]的值int currentSum = ans[bottom+1][col+1] - ans[top][col+1];// prefix[i−1]=prefix[j]−target 这个公式的提现if (sumCount.find(currentSum-target) != sumCount.end()) {res += sumCount[currentSum-target];}sumCount[currentSum]++;}}}return res;
}