Java Solution with Detailed Explanation
Before this problem\n>https://leetcode.com/problems/subarray-sum-equals-k/\n>https://leetcode.com/problems/subarray-sum-equals-k/discuss/803317/Java-Solution-wi
## Before this problem\n>https://leetcode.com/problems/subarray-sum-equals-k/\n>https://leetcode.com/problems/subarray-sum-equals-k/discuss/803317/Java-Solution-with-Detailed-Explanation\n## Thinkings\n\n1.  For a matrix, what is the prefix sum ?\n\n\t   sum[x] [y] is the sum of submatrix \n\n\t   (The upper left corner is matrix[0] [0], the lower right corner is matrix[x] [y])\n\n\t  ![image](https://assets.leetcode.com/users/images/da24efb3-690d-487a-b40f-8afb366907b8_1597987444.885463.png)\n\n\n2. How to calculate the sum of all submatrices ***whose upper left corners are matrix[0] [0]*** \uFF1F\n\n   Step 1. Calculate the prefix sum of each line.\n\n\t  ![image](https://assets.leetcode.com/users/images/04f9a388-d83a-499c-b7bf-2423a0e4833e_1597987466.6122327.png)\n\n\n   ```java\n   // Like the one-dimensional prefix sum, \n   // in order to prevent index out of range and facilitate calculations,\n   // we add an extra column with all 0s at the forefront.\n   int line = matrix.length;\n   int column = matrix[0].length + 1;\n   int[][] sum = new int[line][column]; // Initialization default is all 0\n           \n   for (int l = 0; l < sum.length; l++){\n     // start from the second column\n     for (int c = 1; c < sum[0].length; c++){\n       sum[l][c] = sum[l][c - 1] + matrix[l][c - 1]; // "c - 1",because of an extra column.\n     }\n   }\n   ```\n\n\t  ![image](https://assets.leetcode.com/users/images/36d2c68a-1682-4e79-9eb2-84f12b4d0677_1597987495.016029.png)\n\n\n   Step 2. Using the prefix sum of each line to calculate the sum of submatrix.\n\n   ![image](https://assets.leetcode.com/users/images/bdd7351c-95df-4c5d-be1a-eed32d7c9057_1597987518.405201.png)\n\n\n   ```java\xA0\n   sum[1][2] = sum[1][2] + sum[0][2]; // green + orange\n   ```\n\n   ```java\n   sum[2][2] = sum[2][2] + sum[1][2] + sum[0][2]; // blue + green + orange\n   ```\n\n   So, to caculate any sum of submatrices ***whose upper left corner are matrix[0] [0].***\n\n   ```java\n   int sumOfSubMatrix = 0;\n   \n   for(int l = 0; l < line; l++){\n   \tsumOfSubMatrix += sum[l][column]; // one of submatrices\n   }\n   ```\n\n\n\n3. How to find all submatrices ?\n\n   1. Any submatrix needs any two rows and any two columns to form, that is to say, four variables and four nested loops are required.\n\n      ```java\n      // Use double nested "for" loop to select any two columns\n      for (int start = 0; start < column; start++){\n                  for (int end = start + 1; end < column; end++ ){\n                    \t// ...\n                    \t// Then Use double nested "for" loop to select any two lines\n                  \t}\n                  }\n      ```\n\n   2. Convert 2D to 1D\n\n      Step 1 : Use the ***prefix sum of each row*** to calculate the matrix sum between the "start" column and "end" column.\n\n      ![image](https://assets.leetcode.com/users/images/14f2cef5-3e35-4d80-abfa-184c6c58b3a0_1597986571.6869073.png)\n\n\n      Step 2 : Rotate it 90 degrees to the left, ***it can be regarded as a one-dimensional array.***\n\n\t\t ![image](https://assets.leetcode.com/users/images/5c6c40f3-55ab-4af5-b090-f0b32c018c9e_1597986584.019118.png)\n\n\n      Then the problem is transformed into how many sub-arrays whose sum == target ?\n\n      ***It\'s the same with >https://leetcode.com/problems/subarray-sum-equals-k/***\n\n      Step 3 : In the same way, we can use hashmap to optimize the double nested loop for any two lines, and only need one loop\n\n      ```java\n      int sumOfSubMatrix = 0;\n      Map<Integer, Integer> map = new HashMap<Integer, Integer>();\n      map.put(0, 1);\n      \n      for(int l = 0; l < line; l++){\n        // prefix sum\n      \tsumOfSubMatrix += sum[l][end] - sum[l][start];\n        \n      \tif (map.containsKey(sumOfSubMatrix - target))\n      \t\tcount += map.get(sumOfSubMatrix - target);\n        \n      \tmap.put(sumOfSubMatrix, map.getOrDefault(sumOfSubMatrix, 0) + 1);\n      ```\n\n      \n\n      \n\n## Code\n\n```java\nclass Solution {\n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        int count = 0;\n        int line = matrix.length;\n        int column = matrix[0].length + 1;\n        int[][] sum = new int[line][column];\n        \n        for (int i = 0; i < sum.length; i++){\n            for (int j = 1; j < sum[0].length; j++){\n                sum[i][j] = sum[i][j - 1] + matrix[i][j - 1];\n            }\n        }\n        \n        \n        for (int start = 0; start < column; start++){\n            for (int end = start + 1; end < column; end++ ){\n                \n                int sumOfSubMatrix = 0;\n                Map<Integer, Integer> map = new HashMap<Integer, Integer>();\n                map.put(0, 1);\n                for(int l = 0; l < line; l++){\n                    sumOfSubMatrix += sum[l][end] - sum[l][start];\n                    if (map.containsKey(sumOfSubMatrix - target))\n                        count += map.get(sumOfSubMatrix - target);\n                    map.put(sumOfSubMatrix, map.getOrDefault(sumOfSubMatrix, 0) + 1);\n                    \n                }\n            }\n        }\n        \n        return count;\n        \n    }\n}\n```\n\n\n\n## Update\nFor the commet from jun.\n1. What\'s the meaning of this sentence ?\n+ "Any submatrix needs any two rows and any two columns to form, that is to say, four variables and four nested loops are required." \n\n\teg. |0| is the submatrix I want to find, whose index is [0][0]\n\tIn the "sum", the column 1 corresponds to column 0 in "matrix".  SO we bound the area like this\n![image](https://assets.leetcode.com/users/images/3637adc2-9111-4232-8ce2-0195bf164e03_1618829866.7781012.png)\n\nSince we have done prefix sum for every line, we need to do sum[line][end_column] - sum[line][start_column], and in this case elements in start_column is all 0, when we subtract sum[line][0], It actually did nothing.\n\nAlso, since "end_cloumn" starts from "end_cloumn = start_column + 1", it is impossible to treat the first column of "sum" as part of our result.\n![image](https://assets.leetcode.com/users/images/bef01364-0496-400b-867e-c664f40b084d_1618830124.2679777.png)\n\n\n\n\n
['Prefix Sum', 'Java']