classSolution { private: intsubarraySum(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: intnumSubmatrixSumTarget(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; } };
publicclassSolution { publicintNumSubmatrixSumTarget(int[][] matrix, int target) {
int ans = 0; int m = matrix.Length, n = matrix[0].Length; for (int i = 0; i < m; ++i) { // 枚举上边界 int[] sum = newint[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; }
publicintSubarraySum(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; } }
funcsubarraySum(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 }
funcnumSubmatrixSumTarget(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 }
classSolution: defnumSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int: defsubarraySum(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 inrange(m): total = [0] * n # 枚举下边界 for j inrange(i, m): for c inrange(n): # 更新每列的元素和 total[c] += matrix[j][c] ans += subarraySum(total, target) return ans
structHashTable { int key, val; UT_hash_handle hh; };
intsubarraySum(int* nums, int numsSize, int k) { structHashTable* hashTable =NULL; structHashTable* 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; }
intnumSubmatrixSumTarget(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; }
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 = newArray(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; }
constsubarraySum = (nums, k) => { const map = newMap(); 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)) 的时间复杂度。