Maximum Side Length of a Square with Sum Less than or Equal to Threshold

给一个2d数组, 给一个数threshold. 返回最大的square的边长, 能让里面的数字和等于或者小于 threshold. 这个题主要考察presum的范围理解, 我们用presum的时候,因为扫描数组是从左往右从上到下, 所以我们想用squares的范围的时候, 需要减去重复的部分. 比如, sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + mat[i][j]; 而不能单纯的sum[i+1][j+1] + mat[i][j] 同理, 当我们检查是否有新的max的时候, 也是用这个方法. 我看到答案里面有别的做法, 比如用二分搜索+测试, 我觉得没必要, 因为复杂度不可能少于O(M*N), 因为不看到最后一个, 怎么知道是不是有可能有最大的square.