1074. Number of Submatrices That Sum to Target

二刷 07/2022

Version #2 Prefix Sum by Row

比之前的方法少了一个dimension，因为用到了hashmap记录了之前prefixsum的值

Time O(M^2N)

Space O(MN)

Runtime: 276 ms, faster than 45.16% of Java online submissions for Number of Submatrices That Sum to Target.

Memory Usage: 117.6 MB, less than 37.22% of Java online submissions for Number of Submatrices That Sum to Target.

class Solution {

    public int numSubmatrixSumTarget(int[][] matrix, int target) {

        int rows = matrix.length;

        int cols = matrix[0].length;

        int[][] prefixSums = new int[rows][cols + 1];

        for (int y = 0; y < rows; y++) {

            for (int x = 1; x <= cols; x++) {

                prefixSums[y][x] = prefixSums[y][x - 1] + matrix[y][x - 1];

            }

        }

        int result = 0;

        // prefixSum[i] - sum from element [0, i - 1]

        // prefixSum[end] - prefixSum[start] - sum [start, end)

        for (int start = 0; start < cols; start++) {

            for (int end = start + 1; end <= cols; end++) {

                Map<Integer, Integer> map = new HashMap<>();

                int sum = 0;

                map.put(0, 1);

                for (int y = 0; y < rows; y++) {

                    sum += prefixSums[y][end] - prefixSums[y][start];

                    // sum - prevSum = target

                    result += map.getOrDefault(sum - target, 0);

                    map.put(sum, map.getOrDefault(sum, 0) + 1);

                }

            }

        }

        return result;

    }

}

 一刷 07/2022

Version #1 Square Prefix Sum Brute Force

Time O(M^2N^2)

Space O(MN)

Runtime: 351 ms, faster than 18.36% of Java online submissions for Number of Submatrices That Sum to Target.

Memory Usage: 45.8 MB, less than 76.92% of Java online submissions for Number of Submatrices That Sum to Target.

class Solution {

    public int numSubmatrixSumTarget(int[][] matrix, int target) {

        int rows = matrix.length;

        int cols = matrix[0].length;

        long[][] sums = new long[rows + 1][cols + 1];

        for (int y = 0; y <= rows; y++) {

            for (int x = 0; x <= cols; x++) {

                if (y == 0 || x == 0) {

                    sums[y][x] = 0;

                    continue;

                }

                sums[y][x] = matrix[y - 1][x - 1] + sums[y - 1][x] + sums[y][x - 1] - sums[y - 1][x - 1];

            }

        }

        int result = 0;

        //  (top,left)  (top,right)

        //  (down,left) (down,right)

        for (int top = 0; top < rows; top++) {

            for (int down = top + 1; down <= rows; down++) {

                for (int left = 0; left < cols; left++) {

                    for (int right = left + 1; right <= cols; right++) {

                        if (sums[down][right] - sums[top][right] - sums[down][left] + sums[top][left] == target) {

                            result++;

                        }

                    }

                }

            }

        }

        return result;

     }

}