Rust | Prefix Sum | simple solution
Complexity\n- Time complexity: O(n^4)\n\n- Space complexity: O(n^2)\n\n# Code\n\nimpl Solution {\n    pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, tar
# Complexity\n- Time complexity: $$O(n^4)$$\n\n- Space complexity: $$O(n^2)$$\n\n# Code\n```\nimpl Solution {\n    pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 {\n        let (m, n) = (matrix.len(), matrix[0].len());\n        let mut psum = vec![vec![0; n+1]; m+1];\n        for i in 0..m {\n            for j in 0..n {\n                psum[i+1][j+1] = matrix[i][j] + psum[i+1][j] + psum[i][j+1] - psum[i][j];\n            }\n        }\n        let mut ans = 0;\n        for x_bottom in 1..=m {\n            for y_bottom in 1..=n {\n                let psum_bottom = psum[x_bottom][y_bottom];\n                for x_top in 1..=x_bottom {\n                    let diff1 = psum[x_top-1][y_bottom];\n                    for y_top in 1..=y_bottom {\n                        if psum_bottom - diff1 - psum[x_bottom][y_top-1] + psum[x_top-1][y_top-1] == target {\n                            ans += 1;\n                        }\n                    }\n                }\n            }\n        }\n        ans\n    }\n}\n```
['Rust']