力扣 1074. 元素和为目标值的子矩阵数量

题目描述

给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。

如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。

示例 1：

输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0输出：4解释：四个只含 0 的 1x1 子矩阵。

示例 2：

输入：matrix = [[1,-1],[-1,1]], target = 0输出：5解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。

示例 3：

输入：matrix = [[904]], target = 0输出：0

提示：

1 <= matrix.length <= 1001 <= matrix[0].length <= 100-1000 <= matrix[i] <= 1000-10^8 <= target <= 10^8

解决方案

方法一：前缀和 + 哈希表

我们枚举子矩阵的上下边界，并计算出该边界内每列的元素和，则原问题转换成了如下一维问题：

给定一个整数数组和一个整数 target，计算该数组中子数组和等于 target 的子数组个数。

力扣上已有该问题：560. 和为K的子数组，读者可以参考其官方题解，并掌握使用前缀和+哈希表的线性做法。

对于每列的元素和 sum 的计算，我们在枚举子矩阵上边界 i 时，初始下边界 j 为 i，此时 sum 就是矩阵第 i 行的元素。每次向下延长下边界 j 时，我们可以将矩阵第 j 行的元素累加到 sum 中。

C++

class Solution {private:    int subarraySum(vector<int> &nums, int k) {        unordered_map<int, int> mp;        mp[0] = 1;        int count = 0, pre = 0;        for (auto &x:nums) {            pre += x;            if (mp.find(pre - k) != mp.end()) {                count += mp[pre - k];            }            mp[pre]++;        }        return count;    }public:    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {        int ans = 0;        int m = matrix.size(), n = matrix[0].size();        for (int i = 0; i < m; ++i) { // 枚举上边界            vector<int> sum(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;    }};

Java

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;    }}

C#

public 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) {        Dictionary<int, int> dictionary = new Dictionary<int, int>();        dictionary.Add(0, 1);        int count = 0, pre = 0;        foreach (int x in nums) {            pre += x;            if (dictionary.ContainsKey(pre - k)) {                count += dictionary[pre - k];            }            if (!dictionary.ContainsKey(pre)) {                dictionary.Add(pre, 1);            } else {                ++dictionary[pre];            }        }        return count;    }}

Golang

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}

Python3

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

C

struct HashTable {    int key, val;    UT_hash_handle hh;};int subarraySum(int* nums, int numsSize, int k) {    struct HashTable* hashTable = NULL;    struct HashTable* tmp = malloc(sizeof(struct HashTable));    tmp->key = 0, tmp->val = 1;    HASH_ADD_INT(hashTable, key, tmp);    int count = 0, pre = 0;    for (int i = 0; i < numsSize; i++) {        pre += nums[i];        int x = pre - k;        HASH_FIND_INT(hashTable, &x, tmp);        if (tmp != NULL) {            count += tmp->val;        }        HASH_FIND_INT(hashTable, &pre, tmp);        if (tmp != NULL) {            tmp->val++;        } else {            tmp = malloc(sizeof(struct HashTable));            tmp->key = pre, tmp->val = 1;            HASH_ADD_INT(hashTable, key, tmp);        }    }    return count;}int numSubmatrixSumTarget(int** matrix, int matrixSize, int* matrixColSize, int target) {    int ans = 0;    int m = matrixSize, n = matrixColSize[0];    for (int i = 0; i < m; ++i) {  // 枚举上边界        int sum[n];        memset(sum, 0, sizeof(sum));        for (int j = i; j < m; ++j) {  // 枚举下边界            for (int c = 0; c < n; ++c) {                sum[c] += matrix[j][c];  // 更新每列的元素和            }            ans += subarraySum(sum, n, target);        }    }    return ans;}

JavaScript

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;}

复杂度分析

时间复杂度：

其中 m 和 n 分别是矩阵 matrix 的行数和列数。

空间复杂度：O(n)。

优化

若行数大于列数，枚举矩形的左右边界更优，对应的时间复杂度为

总之，根据 m 和 n 的大小来细化枚举策略，我们可以做到

的时间复杂度。

BY /

本文作者：力扣

编辑&版式：霍霍

声明：本文归“力扣”版权所有，如需转载请联系。