java 解法, 执行用时: 130 ms, 内存消耗: 42.8 MB, 提交时间: 2023-06-01 09:45:57

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int ans = 0;
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; ++i) { // 枚举上边界
            int[] sum = new int[n];
            for (int j = i; j < m; ++j) { // 枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // 更新每列的元素和
                }
                ans += subarraySum(sum, target);
            }
        }
        return ans;
    }

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 1);
        int count = 0, pre = 0;
        for (int x : nums) {
            pre += x;
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

golang 解法, 执行用时: 136 ms, 内存消耗: 7 MB, 提交时间: 2023-06-01 09:45:39

func subarraySum(nums []int, k int) (ans int) {
    mp := map[int]int{0: 1}
    for i, pre := 0, 0; i < len(nums); i++ {
        pre += nums[i]
        if _, ok := mp[pre-k]; ok {
            ans += mp[pre-k]
        }
        mp[pre]++
    }
    return
}

func numSubmatrixSumTarget(matrix [][]int, target int) (ans int) {
    for i := range matrix { // 枚举上边界
        sum := make([]int, len(matrix[0]))
        for _, row := range matrix[i:] { // 枚举下边界
            for c, v := range row {
                sum[c] += v // 更新每列的元素和
            }
            ans += subarraySum(sum, target)
        }
    }
    return
}

javascript 解法, 执行用时: 192 ms, 内存消耗: 48.5 MB, 提交时间: 2023-06-01 09:45:23

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {number}
 */
var numSubmatrixSumTarget = function(matrix, target) {
    let ans = 0;
    const m = matrix.length, n = matrix[0].length;
    for (let i = 0; i < m; ++i) { // 枚举上边界
        const sum = new Array(n).fill(0);
        for (let j = i; j < m; ++j) { // 枚举下边界
            for (let c = 0; c < n; ++c) {
                sum[c] += matrix[j][c]; // 更新每列的元素和
            }
            ans += subarraySum(sum, target);
        }
    }
    return ans;
}

const subarraySum = (nums, k) => {
    const map = new Map();
    map.set(0, 1);
    let count = 0, pre = 0;
    for (const x of nums) {
        pre += x;
        if (map.has(pre - k)) {
            count += map.get(pre - k);
        }
        map.set(pre, (map.get(pre) || 0) + 1);
    }
    return count;
}

python3 解法, 执行用时: 768 ms, 内存消耗: 16.8 MB, 提交时间: 2023-06-01 09:45:08

# 前缀和 + 哈希表
class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        def subarraySum(nums: List[int], k: int) -> int:
            mp = Counter([0])
            count = pre = 0
            for x in nums:
                pre += x
                if pre - k in mp:
                    count += mp[pre - k]
                mp[pre] += 1
            return count
        
        m, n = len(matrix), len(matrix[0])
        ans = 0
        # 枚举上边界
        for i in range(m):
            total = [0] * n
            # 枚举下边界
            for j in range(i, m):
                for c in range(n):
                    # 更新每列的元素和
                    total[c] += matrix[j][c]
                ans += subarraySum(total, target)
        
        return ans