Rust: Prefix Sum DP + HashMap for O(m * n * n)
Firstly make a basic prefix sum DP solution for O(m * m * n * n) time.\nrust\npub fn num_submatrix_sum_target_old(matrix: Vec<Vec<i32>>, target: i32) -> i32 {\n
Firstly make a basic prefix sum DP solution for O(m * m * n * n) time.\n```rust\npub fn num_submatrix_sum_target_old(matrix: Vec<Vec<i32>>, target: i32) -> i32 {\n    let mut dp = vec![vec![0; matrix[0].len() + 1]; matrix.len() + 1];\n    let mut ans = 0;        \n    for i in 0..matrix.len() {\n        for j in 0..matrix[0].len() {\n            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + matrix[i][j];\n            for x in 0..i + 1 {\n                for y in 0..j + 1 {\n                    if dp[i + 1][j + 1] - dp[i + 1][y] - (dp[x][j + 1] - dp[x][y]) == target {\n                        ans += 1;\n                    }\n                }\n            }\n        }\n    }\n    ans\n}\n```\nThen we can find that the count of previous results of `dp[x][j + 1] - dp[x][y]` can be grouped up with a HashMap. Simple modification but having a O(m * n * n) space HashMap.\n```rust\npub fn num_submatrix_sum_target_hash(matrix: Vec<Vec<i32>>, target: i32) -> i32 {\n    let mut dp = vec![vec![0; matrix[0].len() + 1]; matrix.len() + 1];\n    let mut ans = 0;        \n    let mut hash: HashMap<(usize, usize, i32), i32> = HashMap::new();\n    for j in 0..matrix[0].len() {\n        for y in 0..j + 1 {\n            hash.insert((y, j + 1, 0), 1);\n        }\n    }\n    for i in 0..matrix.len() {\n        for j in 0..matrix[0].len() {\n            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + matrix[i][j];\n            for y in 0..j + 1 {\n                let diff = dp[i + 1][j + 1] - dp[i + 1][y];\n                if let Some(c) = hash.get(&(y, j + 1, diff - target)) {\n                    ans += c;\n                }\n                *hash.entry((y, j + 1, diff)).or_insert(0) += 1;\n            }\n        }\n    }\n    ans\n}\n```\nThen optimize the HashMap space usage by eliminating the `(y, j + 1)` part, making it O(n) space.\n```rust\npub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 {\n    let mut dp = vec![vec![0; matrix[0].len() + 1]; matrix.len() + 1];\n    let mut ans = 0;\n    for i in 0..matrix.len() {\n        for j in 0..matrix[0].len() {\n            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + matrix[i][j];\n        }\n    }\n    for j in 0..matrix[0].len() {\n        for y in 0..j + 1 {\n            let mut hash: HashMap<i32, i32> = HashMap::new();\n            hash.insert(0, 1);\n            for i in 0..matrix.len() {\n                let diff = dp[i + 1][j + 1] - dp[i + 1][y];\n                if let Some(c) = hash.get(&(diff - target)) {\n                    ans += c;\n                }\n                *hash.entry(diff).or_insert(0) += 1;\n            }\n        }\n    }\n    ans\n}\n```
['Prefix Sum', 'Rust']