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

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

题面

leetcode题目

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

子矩阵 \(x_1, y_1, x_2, y_2\) 是满足 \(x_1\leq x\leq x_2\) 且 \(y_1\leq y\leq y_2\) 的所有单元 \(matrix[x][y]\) 的集合。

如果 \((x_1, y_1, x_2, y_2)\) 和 \((x_1^{'}, y_1^{'}, x_2^{'}, y_2^{'})\) 两个子矩阵中部分坐标不同（如：\(x_1\neq x_1^{'}\)），那么这两个子矩阵也不同。

example

示例

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

数据范围

• \(1 \leq matrix.length \leq 100\)
• \(1 \leq matrix[0].length \leq 100\)
• \(-1000 \leq matrix[i] \leq 1000\)
• \(-10^8 \leq target \leq 10^8\)

题解

总体思路

一个比较的想法是枚举所有可能的子矩阵情况，计算子矩阵的和，与\(target\)做比较，统计结果即可。
令\(matrix.length = m\) , \(matrix[0].length = n\) 。那么显然我们这种想法的时间复杂度为\(O(m^3n^3)\)，我们需要考虑进行优化。
枚举子矩阵这一步已经很难进行优化了，我们将优化的目标放在计算子矩阵的和上，我们首先考虑如何去遍历子矩阵，一种简单的想法是遍历矩阵的所有元素，以这个元素为起点，向左上角(假设以\(matrix[0][0]\)向右下角方向建系)枚举所有可能的情况。对于所有的子矩阵，我们都可以以两个坐标点来表示他，即从左上角\((x_1,y_1)\)到右下角\((x_2,y_2)\)。计算这个矩阵的和，其实可以这样考虑： 假设左上角为坐标原点，右下角为\((x_2,y_2)\)的坐标点，其中黄紫蓝交替的点为\((x_1,y_1)\)，那么其实只需要计算整个矩阵的和，减去两个紫色加黄色的部分，再加上一份黄色的和即可。即令\(sum(x,y) = f(x,y) = matrix[0][0] + matrix[0][1] + \dots + matrix[x][y]\)，那么子矩阵的和为\(f(x_2,y_2) - f(x_2 - x_1, y_2) - f(x_2, y_2 - y_1) + f(x_2 - x_1, y_2 - y_1)\)。只要能够在\(O(1)\)的时间内计算出\(f(x,y)\)的值，那么我们整体的时间复杂度就优化到了\(O(m^2n^2)\)。
考虑\(f(x,y)\)的维护，令\(f^{'}(x,y) = matrix[x][0] + matrix[x][1] + \cdots + matrix[x][y]\)，那么\(f(x,y) = f(x-1,y) + f^{'}(x,y)\)。这里我们可以参考下图，整个矩阵的元素和，等于其蓝色部分加上橙色部分。 我们可以很显然的看出\(f^{'}(x,y)\)可以通过前缀和维护，在存在\(f^{'}(x,y)\)的情况下，\(f(x,y)\)也可以通过前缀和维护。

代码

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
//#define _DEBUG
//#define _DEBUG_1
//#define _DEBUG_2
using namespace std;
class Solution
{
#ifdef _DEBUG
#define MAX 10
#else
#define MAX 101
#endif

public:
    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target)
    {
        int preX[MAX][MAX];
        int preY[MAX][MAX];
        memset(preX, 0, sizeof(preX));
        memset(preY, 0, sizeof(preY));
        int len = matrix[0].size();
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = 0; j < len; j++)
            {
                int num = matrix[i][j];
                int pre = 0;
                if (i - 1 >= 0)
                {
                    pre = preY[i - 1][j];
                }
                preY[i][j] = pre + num;
            }
        }
        for (int j = 0; j < len; j++)
        {
            for (int i = 0; i < matrix.size(); i++)
            {
                int num = matrix[i][j];
                int pre = 0;
                if (j - 1 >= 0)
                {
                    pre = preX[i][j - 1];
                }
                preX[i][j] = pre + preY[i][j];
            }
        }

#ifdef _DEBUG
        cout << "preY:" << endl;
        printVector(preY, len);
        cout << "preX:" << endl;
        printVector(preX, len);
#endif

        int ret = 0;
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = 0; j < len; j++)
            {
                for (int lenX = 1; lenX <= i + 1; lenX++)
                {
                    for (int lenY = 1; lenY <= j + 1; lenY++)
                    {
                        int sub1, sub2, add1;
                        sub1 = sub2 = add1 = 0;
                        if (i - lenX >= 0)
                        {
                            sub1 = preX[i - lenX][j];
                        }
                        if (j - lenY >= 0)
                        {
                            sub2 = preX[i][j - lenY];
                        }
                        if (i - lenX >= 0 && j - lenY >= 0)
                        {
                            add1 = preX[i - lenX][j - lenY];
                        }
                        int sum = preX[i][j] - sub1 - sub2 + add1;
#ifdef _DEBUG
                        cout << "i: " << i << " j: " << j << " lenX: " << lenX << " lenY: " << lenY << " sum: " << sum << endl;
#endif
                        if (sum == target)
                        {
                            ret++;
                        }
                    }
                }
            }
        }
        return ret;
    }
    int min(int a, int b)
    {
        if (a < b)
        {
            return a;
        }
        return b;
    }
    int max(int a, int b)
    {
        if (a > b)
        {
            return a;
        }
        return b;
    }
    void printVector(int a[][MAX], int len)
    {
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < len; j++)
            {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
    }
};

// for test
int main()
{
    Solution s;
    vector<vector<int>> test1 = {{0, 1, 0},
                                 {1, 1, 1},
                                 {0, 1, 0}};
    vector<vector<int>> test2 = {{1, -1}, {-1, 1}};
    vector<vector<int>> test3 = {{904}};
    cout << s.numSubmatrixSumTarget(test1, 0) << endl;
    cout << s.numSubmatrixSumTarget(test2, 0) << endl;
    cout << s.numSubmatrixSumTarget(test3, 0) << endl;

    return 0;
}