Simple beginner-level C solution || Prefix sum + Brute force || With clear comments || 中文註解
\n# Complexity\n- Time complexity:  $O(m^2n^2)$\n- Space complexity: $O(mn)$\n Add your space complexity here, e.g. O(n) \n\n# Code\ncpp\n// 1074. Number of Sub
\n# Complexity\n- Time complexity:  $O(m^2n^2)$\n- Space complexity: $O(mn)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp\n// 1074. Number of Submatrices That Sum to Target\nint** init_2D_array(const int arrSize, const int arrColSize) {\n    int** arr = (int**)calloc(arrSize, sizeof(int*));\n    for (int i = 0; i < arrSize; i++) {\n        arr[i] = (int*)calloc(arrColSize, sizeof(int));\n    }\n    return arr;\n}\nvoid free_2D_array(int*** arr, const int arrSize, const int arrColSize) {\n    for (int i = 0; i < arrSize; i++) {\n        free((*arr)[i]);\n    }\n    free((*arr));\n}\nint numSubmatrixSumTarget(int** matrix, int matrixSize, int* matrixColSize, int target) {\n    // Prefix sum + Brute force\n\n    // Time complexity: O(m^2*n^2)\n    // Space complexity: O(m*n)\n\n    // Given a 2D matrix of size m x n and an integer target \n    // Find the number of non-empty submatrices whose sum equals target\n\n    const int m = matrixSize, n = matrixColSize[0];\n    int result = 0;  // Record the occurrence count\n    \n    // Use prefix sum matrix to quickly compute the sum of any submatrix\n    int** sums = init_2D_array(m + 1, n + 1);\n\n    // Traverse matrix starting from 1 to build the prefix sum matrix \'sums\'\n    for (int i = 1; i <= m; i++) {\n        for (int j = 1; j <= n; j++) {\n            // The sum at current position equals the sum above plus the sum on the left minus \n            // the sum on the upper left plus the value of current position in the original matrix\n            sums[i][j] = sums[i][j - 1] + sums[i - 1][j] - sums[i - 1][j - 1] + matrix[i - 1][j - 1];\n        }\n    }\n\n    // Then traverse all possible submatrix cases. \n\n    // Since a matrix has 4 vertices, the time complexity of traversal is O(n^4). By accessing the \n    // results of the prefix sum matrix \'sums\' with coordinates of the 4 vertices, we can obtain the \n    // sum of the submatrix in O(1) time.\n\n    int temp = 0;  // If the calculated value \'temp\' equals target, then increment \'result\'.\n    for (int i = 1; i <= m; i++) {\n        for (int j = 1; j <= n; j++) {\n            for (int p = 1; p <= i; p++) {\n                for (int q = 1; q <= j; q++) {\n                    temp = sums[i][j] - sums[i][q - 1] - sums[p - 1][j] + sums[p - 1][q - 1];\n                    if (temp == target) result++;\n                }\n            }\n        }\n    }\n    free_2D_array(&sums, m + 1, n + 1);\n    return result;\n}\n```\n```cpp\n// 1074. Number of Submatrices That Sum to Target\nint numSubmatrixSumTarget(int** matrix, int matrixSize, int* matrixColSize, int target) {\n    // Prefix sum + Brute force\n\n    // Time complexity: O(m^2*n^2)\n    // Space compelxity: O(m*n)\n\n    // \u7D66\u5B9A\u4E00\u500B\u5927\u5C0F\u70BA m x n \u7684\u4E8C\u7DAD\u77E9\u9663 matrix \u548C\u4E00\u500B\u6574\u6578 target \n    // \u8A66\u554F\u6709\u5E7E\u7A2E \u975E\u7A7A\u5B50\u77E9\u9663\u548C\u7B49\u65BC target \u7684\u60C5\u6CC1\n\n    const int m = matrixSize, n = matrixColSize[0];\n    int result = 0;  // \u8A18\u9304\u60C5\u6CC1\u51FA\u73FE\u7684\u6B21\u6578\n    \n    // \u901A\u904E\u5EFA\u7ACB\u7D2F\u52A0\u548C\u77E9\u9663 \u4F86\u5FEB\u901F\u6C42\u51FA\u4EFB\u610F\u5B50\u77E9\u9663\u7684\u548C\n    int** sums = init_2D_array(m + 1, n + 1);\n\n    // \u5F9E 1 \u958B\u59CB\u904D\u6B77 matrix \u5EFA\u7ACB\u7D2F\u52A0\u548C\u77E9\u9663\u65BC sums\n    for (int i = 1; i <= m; i++) {\n        for (int j = 1; j <= n; j++) {\n            // \u7576\u524D\u4F4D\u7F6E\u7D2F\u52A0\u548C \u7B49\u65BC \u4E0A\u9762\u7684\u503C \u52A0\u4E0A\u5DE6\u908A\u7684\u503C \u6E1B\u53BB\u5DE6\u4E0A\u7684\u503C \u6700\u5F8C\u52A0\u4E0A\u539F\u77E9\u9663\u4E2D\u7576\u524D\u4F4D\u7F6E\u7684\u503C\n            sums[i][j] = sums[i][j - 1] + sums[i - 1][j] - sums[i - 1][j - 1] + matrix[i - 1][j - 1];\n        }\n    }\n\n    // \u63A5\u8457\u904D\u6B77\u6240\u6709\u5B50\u77E9\u9663\u53EF\u80FD\u60C5\u6CC1 \u77E9\u9663\u6709 4 \u500B\u9802\u9EDE \u6240\u4EE5\u904D\u6B77\u6642\u9593\u8907\u96DC\u5EA6\u662F O(n^4) \n    // \u7531 4 \u500B\u9802\u9EDE\u5EA7\u6A19\u53BB\u5B58\u53D6\u7D2F\u52A0\u548C\u77E9\u9663 sums \u7684\u7D50\u679C \u61C9\u8A72\u53EF\u4EE5\u5728 O(1) \u5167\u6C42\u5F97\u5B50\u77E9\u9663\u7684\u548C \n    \n    int temp = 0;  // \u5982\u679C\u8A08\u7B97\u503C temp \u7B49\u65BC target \u5247 result++\n    for (int i = 1; i <= m; i++) {\n        for (int j = 1; j <= n; j++) {\n            for (int p = 1; p <= i; p++) {\n                for (int q = 1; q <= j; q++) {\n                    temp = sums[i][j] - sums[i][q - 1] - sums[p - 1][j] + sums[p - 1][q - 1];\n                    if (temp == target) result++;\n                }\n            }\n        }\n    }\n    free_2D_array(&sums, m + 1, n + 1);\n    return result;\n}\n```
['Array', 'C', 'Matrix', 'Prefix Sum']