[Java] N^4 and N^3 Solutions
Solution 1: N^4 ~ 4500ms\njava\nclass Solution {\n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        int m = matrix.length, n = matrix[
**Solution 1: N^4 ~ 4500ms**\n```java\nclass Solution {\n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        int m = matrix.length, n = matrix[0].length;\n        int[][] sum = new int[m + 1][n + 1];\n        for (int i = 1; i <= m; i++) {\n            for (int j = 1; j <= n; j++) {\n                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];\n            }\n        }\n        int ans = 0;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                for (int u = i + 1; u <= m; u++) {\n                    for (int v = j + 1; v <= n; v++) {\n                        int _sum = sum[u][v] - sum[i][v] - sum[u][j] + sum[i][j];\n                        if (_sum == target) {\n                            ans++;\n                        }\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n}\n```\nComplexity:\n- Time: `O((m*n)^2)`\n- Space: `O(m*n)`\n\n**Solution 2 - N^3 ~ 1000ms**\n```java\nclass Solution {\n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        int m = matrix.length, n = matrix[0].length;\n        for (int i = 0; i < m; i++) {\n            for (int j = 1; j < n; j++) {\n                matrix[i][j] += matrix[i][j - 1];\n            }\n        }\n        int ans = 0;\n        for (int i = 0; i < n; i++) {\n            for (int j = i; j < n; j++) {\n                HashMap<Integer, Integer> map = new HashMap<>();\n                map.put(0, 1);\n                int right = 0;\n                for (int k = 0; k < m; k++) {\n                    right += matrix[k][j] - (i == 0 ? 0 : matrix[k][i - 1]);\n                    int left = right - target;\n                    ans += map.getOrDefault(left, 0);\n                    map.put(right, map.getOrDefault(right, 0) + 1);\n                }\n            }\n        }\n        return ans;\n    }\n}\n```\nComplexity:\n- Time: `O(n*n*m)`\n- Space: `O(m)` for map
[]