29 lines
1000 B
Rust
29 lines
1000 B
Rust
impl Solution {
|
|
pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 {
|
|
let (len_x, len_y) = (matrix.len() + 1, matrix[0].len() + 1);
|
|
let mut matrix_sum = vec![vec![0i32; len_y]; len_x];
|
|
|
|
for x in 1..len_x{
|
|
for y in 1..len_y{
|
|
matrix_sum[x][y] = matrix[x - 1][y - 1] + matrix_sum[x - 1][y] + matrix_sum[x][y - 1] - matrix_sum[x - 1][y - 1];
|
|
}
|
|
}
|
|
|
|
let mut count = 0;
|
|
let mut sum = 0;
|
|
for lt_x in 1..len_x{
|
|
for lt_y in 1..len_y{
|
|
for rb_x in lt_x..len_x{
|
|
for rb_y in lt_y..len_y{
|
|
sum = matrix_sum[rb_x][rb_y] - matrix_sum[lt_x - 1][rb_y] - matrix_sum[rb_x][lt_y - 1] + matrix_sum[lt_x - 1][lt_y - 1];
|
|
if sum == target{
|
|
count += 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return count;
|
|
}
|
|
} |