是否存在O(n²)复杂度求解和为K的正方形子矩阵的方法

• 若输入矩阵的所有元素均为非负数值，存在时间复杂度为O(n²)的求解方法；
• 若矩阵允许包含负数值，目前没有通用的O(n²)复杂度解法，你已经实现的O(n²logn)二分+前缀和方案已经是该场景下的最优实现之一。

该方法基于二维前缀和+对角线双指针实现，逻辑简单、运行常数低：

• 首先用O(n²)时间预处理二维前缀和数组，实现任意子矩阵和的O(1)查询。前缀和递推逻辑如下：
  pre[i][j] = matrix[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]
  其中pre为(n+1)*(n+1)大小的数组，第0行、第0列全部置0，用于省去边界判断的额外逻辑。
• 所有正方形子矩阵的左上角和右下角，必然落在同一条左上-右下走向、满足i-j = 固定值的对角线上，n阶方阵总共有2n-1条这类对角线。我们按对角线为单位分组遍历所有可能的正方形，避免重复计算。
• 对每条对角线使用双指针滑动窗口处理：
  • 初始化左指针（对应正方形左上角坐标）指向对角线的起点，右指针（对应正方形右下角坐标）从对角线起点开始，逐次向对角线末端移动；
  • 由于矩阵元素非负，固定右指针位置时，正方形边长越长（左指针越靠近对角线起点），子矩阵的元素和单调不减。每次移动右指针后，仅需要向右调整左指针位置，直到当前左右指针围成的正方形和不超过K，调整过程中直接判断当前正方形和是否恰好等于K，命中即可直接返回结果；
  • 整条对角线遍历过程中左指针只会右移、不会回退，因此单条对角线的处理耗时为O(n)，所有对角线累计处理耗时为O(n²)。
• 整套流程的总时间复杂度为O(n²)，额外空间开销为O(n²)（如果允许在原矩阵上原地计算前缀和，空间复杂度可降到O(1)，工程上不推荐这么做）。

如果矩阵包含负数，子矩阵和会失去随边长单调递增的性质，双指针的逻辑基础不成立，无法套用上述优化。目前针对含负数矩阵的该问题，通用解法的复杂度下界为O(n²logn)，和你已实现的二分方案性能一致。

内容的提问来源于stack exchange，提问作者Aditya Bhandari