1074.Number of Submatrices That Sum to Target

作者 Lucyyang 日期 2020-03-25
1074.Number of Submatrices That Sum to Target

Just Do It!

一道有趣的二维平面上求连续子区间满足target的题目,可以分解为几个不同的小问题,非常值得学习。先来看下题目LC1074:给定一个矩阵matrix,求有多少个不同的连续子区间的和等于target,注意在二维平面上,连续子区间可以为一维也可以为二维,此外值可以为负数。

这道题目可以拆成两个问题,一是对一个一维数组,有多少连续子区间和为target;二是求一个二维矩阵中和最大的子矩阵,下面就一一解决。

Subarray Sum Equals K

题目:LC560,在给定的数组中,求有多少个子区间和为target。

方法:前缀和+hash table,对每个nums[i],算出前缀和sum[i]后,我们要找是否有前缀和满足sum[i] - sum[x] = target。因此要用一个hash table对每个元素的前缀和进行记录。注意在最开始要在hash table中加入{0, 1},表示前缀和本身。hash table中的第二个值为val出现的次数。

代码:

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int res = 0;
int sum = 0;
unordered_map<int, int> m;
m[0] = 1; // 注意{0, 1}表示不减去任何值时是否相等
for(int i = 0; i < nums.size(); i++) {
sum += nums[i];
if(m.find(sum - k) != m.end())
res += m[sum-k];
m[sum]++;
}
return res;
}
};

Maximum sum rectangle in a 2D matrix

题目:这是一道G4G上的题目,求一个矩阵中和最大的子矩阵。

方法:先用left和right固定矩阵的左右行,并用向量temp来记录每一行的值:

$$temp[i] = \sum_{j = left}^{right}matrix[i][j]$$

然后再判断当前值是否大于maxSum,并进行更新。

代码:

int kadane(int* arr, int* start,
int* finish, int n)
{
// initialize sum, maxSum and
int sum = 0, maxSum = INT_MIN, i;
// Just some initial value to check
// for all negative values case
*finish = -1;
// local variable
int local_start = 0;
for (i = 0; i < n; ++i)
{
sum += arr[i];
if (sum < 0)
{
sum = 0;
local_start = i + 1;
}
else if (sum > maxSum)
{
maxSum = sum;
*start = local_start;
*finish = i;
}
}
// There is at-least one
// non-negative number
if (*finish != -1)
return maxSum;
// Special Case: When all numbers
// in arr[] are negative
maxSum = arr[0];
*start = *finish = 0;
// Find the maximum element in array
for (i = 1; i < n; i++)
{
if (arr[i] > maxSum)
{
maxSum = arr[i];
*start = *finish = i;
}
}
return maxSum;
}
// The main function that finds
// maximum sum rectangle in M[][]
void findMaxSum(int M[][COL])
{
// Variables to store the final output
int maxSum = INT_MIN, finalLeft, finalRight,
finalTop, finalBottom;
int left, right, i;
int temp[ROW], sum, start, finish;
// Set the left column
for (left = 0; left < COL; ++left)
{
// Initialize all elements of temp as 0
memset(temp, 0, sizeof(temp));
// Set the right column for the left
// column set by outer loop
for (right = left; right < COL; ++right)
{
for (i = 0; i < ROW; ++i)
temp[i] += M[i][right];
sum = kadane(temp, &start, &finish, ROW);
if (sum > maxSum)
{
maxSum = sum;
finalLeft = left;
finalRight = right;
finalTop = start;
finalBottom = finish;
}
}
}
cout << "Max sum is: " << maxSum << endl;
}

Number of Submatrices That Sum to Target

那么对于这道稍微复杂的题目,我们先借鉴求submatrix最大和的思想,将复杂度优化到O(MN2),然后通过求一维子区间的方式,对array进行计算,最后复杂度为O((NM)2)。

代码:

class Solution {
public:
int calarray(vector<int> matrix, int target) {
int sum = 0;
int res = 0;
unordered_map<int, int> m;
m[0] = 1;
for(int i = 0; i < matrix.size(); i++) {
sum += matrix[i];
if(m.find(sum-target) != m.end()) {
res += m[sum-target];
}
m[sum]++; //应该是将当前值装入
}
return res;
}
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int res = 0;
if(matrix.size() == 0)
return res;
for(int l = 0; l < matrix[0].size(); l++) {
vector<int> array(matrix.size());
for(int r = l; r < matrix[0].size(); r++) {
for(int k = 0; k < matrix.size(); k++) {
array[k] += matrix[k][r];
}
res += calarray(array, target);
}
}
return res;
}
};