本题可以遍历每个方阵,查看方阵的和sum是否满足条件。这样的时间复杂度是o(N^4),其中遍历每个元素作为方阵的右下角需要o(N^2),随着边长的增长,面积增长的速率是o(N^2)。
本题更高效的方法就是二分搜值。猜测一个边长len,查看是否有一个方阵的sum满足条件。这样的时间复杂度是o(logN*N^2)
.
注意,本题中计算任意一个方阵的元素sum的复杂度是o(1),因为只要提前计算二维的前缀和presum[i][j]即可。例如,以(a,b)为左上角、(x,y)为右下角的矩阵,其元素和就是presum[x][y]-presum[i-1][y]-presum[i][y-1]+presum[i-1][j-1]
.