leetcode_3070——前缀和

元素和小于等于 k 的子矩阵的数目

前缀和

为什么要使用前缀和的方式来写代码？

首先，当然，你可以暴力遍历，由于要求矩阵的元素和的数目，你可以依次先遍历横行，然后再遍历竖行，两个for循环应该就可以搞定。

但是请注意，这样的做法可能无法通过leetcode等软件的测试，因为这样的计算要花费很长的时间。

我向来不相信知乎上有的人说自己用python多快多快，但是用C来运行代码就十分慢。
不正是这么一回事么，自己没写好代码，python上许多的库的质量都非常好，所以python运行起来速度也不慢，但是C上你自己写的函数可不就是能用就行。

所以我们应该如何优化我们的代码？

我们可以注意到，当使用for循环计算的时候，出现了很多重复次数的计算，我们应该避免这些重复计算。

class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int ans = 0,m = grid.size(),n = grid[0].size();
        vector<vector<int>> sum (m+1,vector<int>(n+1));
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] -sum[i][j] + grid[i][j];
                ans += sum[i+1][j+1]<=k;
            }
        }
        return ans;
    }
};

vector<vector<int>> sum (m+1,vector<int>(n+1));先是生成一个答案容器，用来储存数据。

这里需要注意要多申请一点空间，也就是$m+1$与$n+1$，方便用来数据初始化。

然后进行计算。

$\begin{bmatrix} 1 & 2 \\ 2 & 3 \end{bmatrix}$ 类似于这样的一个数组，我们怎么给他进行sum求和？

凭借经验，我们很快可以得到这样的一个结果：

$\begin{bmatrix} 1 & 3 \\ 3 & 8 \end{bmatrix}$ ，那我们是怎么样做的呢？最开始的1，我们不做任何处理，然后右上的2，我们给他加上左边的1，左下的2也是同理，对于右下的3，可以这样抽象，正如左下的2一样，可以给他加上右上的3，然后左边同理，再加上一个3.此时我们可以注意到，1重复了，那么我们就把1给减掉。

sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] -sum[i][j] + grid[i][j];

于是我们就得到了这样的式子。

如果sum[i+1][j+1]符合<=k的条件，那么就说明以grid左上元素到[i][j]这个矩阵的和符合条件。

如此，通过前缀和，我们就实现了对于计算的简化。