Link to the problem

The problem is here: https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/

Background

Let us consider the problem lc-560. Subarray Sum equals K because we need to use some similar idea used in this problem.

lc-560. Subarray Sum equals K

For convenience, the problem description is copied here.

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

  • Input: nums = [1,1,1], k = 2
  • Output: 2

Example 2:

  • Input: nums = [1,2,3], k = 3
  • Output: 2

Constraints:

  • <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

Idea

We define . For simplicity, we also define . We are actually finding the number of different lc-1074. Number of Submatrices That Sum to Target - 图1 pairs s.t. lc-1074. Number of Submatrices That Sum to Target - 图2 (N _is the length of nums) and lc-1074. Number of Submatrices That Sum to Target - 图3, i.e. for some j, we are finding the number of distinct i_ s.t. .

My implementation is this:

  1. int subarraySum(vector<int>& nums, int k) {
  2.     unordered_map<int, int> mp;
  3.     // sum[-1] = 0
  4.     mp[0] = 1;
  5.     int sum = 0;
  6.     int res = 0;
  7.     for (auto n : nums) {
  8.         sum += n;
  9.         int delta = sum - k;
  10.         auto it = mp.find(delta);
  11.         if (it != mp.end()) {
  12.             res += it->second;
  13.         }
  14.         mp[sum]++;
  15.     }
  16.     return res;
  17. }

I used a unordered_map, which is actually a hash table to boost the search of the number of i.

Use subarraySum for lc-1074

We can enumerate x1 and x2. Then we calculate the (sub-)column sum of the values between x1 and x2 for each column and store them in an array csum. Now the problem actually becomes exactly lc-560: csum is nums and target is k.

My implementation is this:

  1. int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
  2.     int m = matrix.size();
  3.     int n = matrix[0].size();
  4.     int res = 0;
  5.     for (int upper = 0; upper < m; upper++) {  // m
  6.         vector<int> csum(n, 0);
  7.         for (int bottom = upper; bottom < m; bottom++) {  // m
  8.             for (int i = 0; i < n; i++) {
  9.                 csum[i] += matrix[bottom][i];
  10.             }
  11.             res += subarraySum(csum, target);  // n
  12.         }
  13.     }
  14.     // O(m^2*n) = 10^6
  15.     return res;
  16. }

It is quite easy with the help of subarraySum.