lc1074.元素和为目标值的子矩阵数量

创建二维前缀和数组

两个for循环，外循环表示子矩阵的左上角（x1,y1），内循环表示子矩阵的右下角（x2,y2）

两个for循环遍历，计算子矩阵的元素总和

四个变量，暴力破解的时间复杂度为O(m^2*n^2)（m、n为matrix数组的行数和列数）

优化

计算每一行的前缀和，而不是整个矩阵的前缀和。

取不同的两个列(j1,j2)，计算以这两个列为边界计算每一行的前缀和（这就是二维前缀和）

这样就可以减少一个变量遍历，时间复杂度为O(m^2*n)（m、n为matrix数组的行数和列数）

代码

import org.junit.Test;import java.util.HashMap;
import java.util.Map;public class SubmatrixNumber {@Testpublic void test() {int[][] matrix = new int[][]{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};
//        for (int[] arr:getPrefixAnd(matrix)) {
//            for (int i:arr) {
//                System.out.print(i+" ");
//            }
//            System.out.println();
//        }System.out.println(submatrixNumber(matrix, 0));//4int[][] matrix1 = new int[][]{{1, -1}, {-1, 1}};System.out.println(submatrixNumber(matrix1, 0));//5int[][] matrix2 = new int[][]{{904}};System.out.println(submatrixNumber(matrix2, 0));//0}public static int submatrixNumber(int[][] matrix, int target) {int[][] sum = getPrefixAnd1(matrix);int ans = 0;Map<Integer, Integer> count = new HashMap<>();//负责记录计算出的每两列之间的前缀和出现的次数int endY = 1;while (endY <= matrix[0].length) {for (int startY = 0; startY < endY; startY++) {//两个列的边界int prefixAnd = 0;count.clear();//两个列的边界不同，此时计算出的前缀和不同，负责记录的map集合需要初始化count.put(0, 1);//当矩阵为空时，需要记录0出现了1次for (int k = 1; k <= matrix.length; k++) {//遍历行prefixAnd += (sum[k][endY] - sum[k][startY]);//计算以这两个列为边界计算每一行的前缀和if (count.containsKey(prefixAnd - target)) {//count集合中是否存在key值为temp-target的数，即为temp-target这个数是否是第一次出现ans += count.get(prefixAnd - target);//不是第一次，则取value值加上}count.put(prefixAnd, count.getOrDefault(prefixAnd, 0) + 1);//记录次数加一//defaultValue - 当指定的key并不存在映射关系中，则返回的该默认值//即如果是第一次出现，则默认的次数记为0}}endY++;}return ans;}public static int[][] getPrefixAnd(int[][] matrix) {int[][] sum = new int[matrix.length][matrix[0].length];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (i == 0 && j > 0) {//第一行sum[i][j] = sum[i][j - 1] + matrix[i][j];} else if (j == 0 && i > 0) {sum[i][j] = sum[i - 1][j] + matrix[i][j];} else if (i == 0 && j == 0) {sum[0][0] = matrix[0][0];} else {sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i][j];}}}return sum;}//sum[0][0] == 0public static int[][] getPrefixAnd1(int[][] matrix) {int[][] sum = new int[matrix.length+1][matrix[0].length+1];for (int i = 1; i <= matrix.length; i++) {for (int j = 1; j <= matrix[0].length; j++) {sum[i][j] = sum[i][j - 1] + matrix[i - 1][j - 1];}}return sum;}
}