给定一个 n x n 的方阵，查找大小为 k x k 的所有子正方形的和

问题陈述

给定一个 n x n 大小的方阵和一个整数 k，我们需要求出该矩阵中所有 k x k 大小的子方阵的和。

例如，我们来看下面这个 4x4 的矩阵

如果 k 是 2，我们需要求出所有 2x2 子方阵的和

子方阵 1

和 = 1 + 2 + 5 + 6 = 14

子方阵 2

和 = 2 + 3 + 6 + 7 = 18

... 以此类推，计算所有可能的 2x2 子方阵。

暴力破解法

一个直接的方法是遍历所有可能的 k x k 大小的子方阵，并单独计算它们的和。这需要使用嵌套循环来遍历矩阵并计算每个子方阵的和。虽然这种方法很直观，但其时间复杂度为 O(n^4)，对于大型矩阵来说效率很低。

输出

时间复杂度

暴力破解法的时间复杂度由用于遍历 n x n 矩阵中所有可能的 k x k 子方阵的嵌套循环决定。这种嵌套循环结构导致的时间复杂度为 O((n - k + 1)^2 * k^2)。

外层的两个循环遍历 (n - k + 1) 行和 (n - k + 1) 列。

内层的两个循环遍历 k x k 的子方阵。

在最坏的情况下，当 k 远小于 n 时，时间复杂度可以近似为 O(n^4)。这是因为与 n^2 相比，(n - k + 1)^2 和 k^2 这两项的贡献会非常大。

方法 2

为高效计算进行预处理

我们可以通过使用一种计算累加和矩阵的预处理技术来显著提高算法的效率。这个想法是创建一个新矩阵，其中每个单元格 (i, j) 存储原始矩阵中从 (0, 0) 开始到 (i, j) 结束的子矩阵中所有元素的和。

例如，给定矩阵

其累加和矩阵将是

一旦我们有了累加和矩阵，我们就可以通过利用其角点元素的和来高效地计算任何子方阵的和。

高效方法

计算累加和矩阵：遍历原始矩阵并构建累加和矩阵。

计算子方阵的和：对于每个大小为 k x k 的子方阵 (i, j)，使用累加和矩阵计算其和

这里，cumSum[i+k][j+k] 是从 (0, 0) 到 (i+k, j+k) 的子矩阵的和，其他项则排除了不属于该子方阵的部分。

输出

对这个时间复杂度有贡献的关键操作是

构建累加和矩阵：用于遍历整个矩阵并计算每个单元格累加和的嵌套循环需要 O(n^2) 的时间。

计算子方阵的和：用于遍历所有可能的 k x k 子方阵的嵌套循环需要 O((n - k + 1)^2) 的时间。由于 'k' 通常小于 'n'，(n - k + 1)^2 项主要由 n^2 项决定，使得整体复杂度为 O(n^2)。

总之，该代码的时间复杂度为 O(n^2)，这比暴力破解法 O(n^4) 的高时间复杂度有了显著的改进，尤其是在处理较大的矩阵和子方阵维度时。