直达链接
主要解题思路分为两个部分，1是构造二维前缀和计算矩阵和，降低每次求和的时间复杂度；2是对所有子矩阵的遍历求和过程，因为需要两个坐标，遍历4个行/列值，4层for循环时间复杂度太高，所以最后两层，在同一个数组中就采用了尺取法（滑动窗口），降低了一层时间复杂度
#include<iostream>
#include<vector>
using namespace std;
int main() {
// 先准备一个二维前缀和
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> prefixSum(n + 1, vector<int>(m + 1, 0));
// 这里要用long long，不然最后三个测试用例int会溢出
long long temp;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> temp;
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + temp;
}
temp = 0;
// 然后怎么检查每个可能的子矩阵？
// 需要两组坐标，4个行/列值，表示一个唯一的子矩阵
for (int row1 = 1; row1 <= n; row1++) {
for (int row2 = row1; row2 <= n; row2++) {
// 尺取法/滑动窗口/双指针，注意循环控制的是右边界，而左边界是我们手动控制的
for (int col1 = 1, col2 = 1; col2 <= m; col2++) {
// 当区间不满足条件（不大于k的时候）
while (col2 >= col1 &&
(prefixSum[row2][col2] - prefixSum[row2][col1 - 1] - prefixSum[row1 - 1][col2] + prefixSum[row1 - 1][col1 - 1]) > k)
col1++;
temp += col2 - col1 + 1;
}
}
}
cout << temp<<endl;
return 0;
}