2020/3/7
题目描述
给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。
示例
示例 1：
输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。
示例 2：
输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
相关标签
数组
动态规划
Sliding window
解题思路
算法：
首先计算矩阵每一列的前缀和，再通过前缀和，对每一子列构造一个 Hashmap，其中保存了这一子列中，val = target - cur 的子矩阵的个数。遍历每一行进行查找并且更新Hashmap。复杂度分析：
时间复杂度：O(mn^2)，其中 m 为行数，n 为列数。需要 mn 此操作来计算矩阵前缀和，另外需要 n 次操作来通过 Hashmap O(1) 时间的查找，得每一列的所有符合要求的子矩阵的个数。
空间复杂度：O(mn+mn^2)，只有几个指针的额外空间
源代码
use std::collections::HashMap;
impl Solution {
pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 {
let (rowm, colm) = (matrix.len(), matrix[0].len());
let mut res = 0;
// prefix_store<(row, col), sum>
let mut prefix_store: HashMap<(usize, usize), i32> = HashMap::new();
// sub_store<(col_start, col_end), [(val1, quantity1), (val2, quantity2), ...]>
let mut sub_store: HashMap<(usize, usize), HashMap<i32, i32>> = HashMap::new();
prefix_store.insert((0, 0), 0);
for row in 1..rowm+1 {
prefix_store.insert((row, 0), 0);
for col in 1..colm+1 {
prefix_store.insert((0, col), 0);
let ans = prefix_store.get(&(row, col-1)).unwrap().clone() +
prefix_store.get(&(row-1, col)).unwrap().clone() -
prefix_store.get(&(row-1, col-1)).unwrap().clone() +
matrix[row-1][col-1].clone();
prefix_store.insert((row, col), ans);
for col_s in 0..col {
sub_store.entry((col_s, col)).or_insert(HashMap::new());
let cur = ans - prefix_store.get(&(row, col_s)).unwrap().clone();
let cur_val = sub_store.get_mut(&(col_s, col)).unwrap();
cur_val.entry(0).or_insert(1);
if let Some(val) = cur_val.get(&(cur-target)) {
res += val;
}
cur_val.entry(cur).or_insert(0);
*cur_val.get_mut(&cur).unwrap() += 1;
}
}
}
res
}
}
执行用时 : 4 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗 : 2.2 MB, 在所有 Rust 提交中击败了100.00%的用户
总结
判断一个序列中，满足子序列之和等于某一值的子序列个数，可以通过hashmap来达到 O(1) 时间复杂度。
对矩阵各个子矩阵的求和可以通过面积加加减减的方法来获得。
