C#如何在大型矩形矩阵中查找求和最大的3x3正方形子矩阵

两种方案的时间复杂度均为O(NM)*，远低于暴力解法的冗余计算开销，适合大尺寸矩阵使用：

方案1：二维前缀和法（通用易维护） #

该方案不限制子矩阵尺寸，后续如果需要调整为k*k的子矩阵查询也不需要改核心逻辑：

• 第一步：预处理和原矩阵等大的二维前缀和矩阵preSum，preSum[i][j]代表原矩阵从左上角(0,0)到(i,j)的矩形区域元素总和
  计算公式：preSum[i][j] = matrix[i][j] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1]，边界位置越位索引统一取值为0即可
• 第二步：遍历所有合法3x3子矩阵的左上角坐标(x,y)，合法范围为x∈[0, N-3]、y∈[0, M-3]，对应右下角坐标为(x+2, y+2)
  子矩阵和计算公式：sum = preSum[x+2][y+2] - preSum[x-1][y+2] - preSum[x+2][y-1] + preSum[x-1][y-1]，越位索引同样取0
• 第三步：遍历过程中记录最大和以及对应的子矩阵坐标即可

方案2：滑动窗口法（3x3专属，常数性能更优） #

针对固定3x3尺寸的场景，可以用两次滑动窗口进一步降低计算常数：

• 第一步：计算每一行长度为3的滑动窗口和，得到N行*(M-2)列的行和矩阵rowSum，rowSum[i][j]代表第i行第j到j+2列的元素和
  每行第一个窗口直接计算3个元素之和，后续窗口仅需要rowSum[i][j] = rowSum[i][j-1] - matrix[i][j-1] + matrix[i][j+2]，单个窗口仅需1次计算
• 第二步：对rowSum的每一列计算长度为3的滑动窗口和，计算结果就是对应3x3子矩阵的总和，列计算同样用滑动逻辑更新
• 第三步：遍历过程中记录最大值即可

边界处理注意事项 #

• 若N<3或M<3，不存在合法3x3子矩阵，可直接返回空或对应异常提示
• 若存在多个和相等的最大子矩阵，可按需求返回第一个出现的结果或所有匹配结果

代码示例（Python 二维前缀和实现） #

def max_3x3_submatrix(matrix):
    n = len(matrix)
    if n < 3:
        return None
    m = len(matrix[0])
    if m < 3:
        return None
    
    # 构建二维前缀和矩阵
    pre_sum = [[0]*m for _ in range(n)]
    for i in range(n):
        row_acc = 0
        for j in range(m):
            row_acc += matrix[i][j]
            pre_sum[i][j] = row_acc
            if i > 0:
                pre_sum[i][j] += pre_sum[i-1][j]
    
    max_sum = float('-inf')
    top_left_pos = (0, 0)
    # 遍历所有合法3x3子矩阵左上角
    for x in range(n - 2):
        for y in range(m - 2):
            cur_sum = pre_sum[x+2][y+2]
            if x > 0:
                cur_sum -= pre_sum[x-1][y+2]
            if y > 0:
                cur_sum -= pre_sum[x+2][y-1]
            if x > 0 and y > 0:
                cur_sum += pre_sum[x-1][y-1]
            
            if cur_sum > max_sum:
                max_sum = cur_sum
                top_left_pos = (x, y)
    
    # 返回最大和、子矩阵左上角坐标
    return max_sum, top_left_pos

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