1074-元素和为目标值的子矩阵数量

Raphael Liu Lv10

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

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2y1 <= 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 <= 100
  • 1 <= 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 中。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
}
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
}
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;
}
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}

复杂度分析

  • 时间复杂度:O(m^2\cdot n)。其中 m 和 n 分别是矩阵 matrix 的行数和列数。

  • 空间复杂度:O(n)。

优化

若行数大于列数,枚举矩形的左右边界更优,对应的时间复杂度为 O(n^2\cdot m)。

总之,根据 m 和 n 的大小来细化枚举策略,我们可以做到 O(\min(m,n)^2\cdot\max(m,n)) 的时间复杂度。


✨扣友帮帮团 - 互动答疑

讨论.jpg{:width=260px}

即日起 - 5 月 30 日,点击 这里  前往「扣友帮帮团 」活动页,把你遇到的问题大胆地提出来,让扣友为你解答~

🎁 奖励规则

被采纳数量排名 1~3 名:「力扣极客套装」 *1 并将获得「力扣神秘应援团」内测资格
被采纳数量排名 4~10 名:「力扣鼠标垫」 *1 并将获得「力扣神秘应援团」内测资格
「诲人不倦」:活动期间「解惑者」只要有 1 个回答被采纳,即可获得 20 LeetCoins 奖励!
「求知若渴」:活动期间「求知者」在活动页发起一次符合要求的疑问帖并至少采纳一次「解惑者」的回答,即可获得 20 LeetCoins 奖励!

活动详情猛戳链接了解更多:🐞 你有 BUG 我来帮 - 力扣互动答疑季

 Comments
On this page
1074-元素和为目标值的子矩阵数量