难度: Medium
3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
示例 1：
输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2] 输出: 1 解释: 下面的子矩阵是一个 3 x 3 的幻方：而这一个不是：
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
示例 2:
输入: grid = [[8]] 输出: 0
提示:
row == grid.lengthcol == grid[i].length1 <= row, col <= 100 <= grid[i][j] <= 15运行时间: 28 ms
内存: 16.0 MB
class Solution:
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
def magic(a,b,c,d,e,f,g,h,i):
return sorted([a,b,c,d,e,f,g,h,i])==list(range(1,10)) and a+b+c==d+e+f==g+h+i==a+d+g==b+e+h==c+f+i==a+e+i==c+e+g==15
m,n=len(grid),len(grid[0])
ans=0
for i in range(m-2):
for j in range(n-2):
if grid[i+1][j+1]!=5:
continue
if magic(grid[i][j],grid[i][j+1],grid[i][j+2],
grid[i+1][j],grid[i+1][j+1],grid[i+1][j+2],
grid[i+2][j],grid[i+2][j+1],grid[i+2][j+2]):
ans+=1
return ans
该题解采用暴力搜索的方法。遍历矩阵中所有可能成为 3x3 幻方的子矩阵的左上角位置。对于每个可能的子矩阵，先检查其中心位置的元素是否为 5，如果不是则跳过该子矩阵。否则，将子矩阵的 9 个元素传入 magic 函数进行验证，如果满足幻方条件则计数加一。最后返回找到的幻方子矩阵数量。magic 函数首先判断传入的 9 个元素是否为 1-9 的排列，然后分别判断行、列、对角线的和是否都等于 15。
时间复杂度: O(mn)
空间复杂度: O(1)
class Solution:
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
def magic(a,b,c,d,e,f,g,h,i):
# 判断传入的9个元素是否为1-9的排列，且行列对角线和都为15
return sorted([a,b,c,d,e,f,g,h,i])==list(range(1,10)) and a+b+c==d+e+f==g+h+i==a+d+g==b+e+h==c+f+i==a+e+i==c+e+g==15
m,n=len(grid),len(grid[0])
ans=0
for i in range(m-2):
for j in range(n-2):
# 判断子矩阵中心是否为5
if grid[i+1][j+1]!=5:
continue
# 传入子矩阵的9个元素进行验证
if magic(grid[i][j],grid[i][j+1],grid[i][j+2],
grid[i+1][j],grid[i+1][j+1],grid[i+1][j+2],
grid[i+2][j],grid[i+2][j+1],grid[i+2][j+2]):
ans+=1
return ans
中心元素为5是3x3幻方的必要条件。在3x3幻方中，中心元素是所有行、列和对角线交汇的点，必须是奇数，且为1到9的中位数。这使得5成为中心元素的唯一选择，因此检查中心是否为5是一个有效的剪枝操作，可以提前排除不可能形成幻方的子矩阵，以减少不必要的计算。
在验证一个矩阵是否为幻方时，除了需要检查行、列和对角线的和是否为15以外，还必须确保矩阵中包含的是1到9的每个数字恰好一次。通过将矩阵中的元素排序后比较是否与列表[1,2,3,4,5,6,7,8,9]相同，可以有效地验证这一条件是否满足。这是因为幻方不仅要求和相等，还要求是由1到9的不重复数字组成。
3x3幻方的定义是所有行、列以及两条主对角线的和必须相等。对于3x3矩阵而言，这个和的值为15，这是基于1到9的所有数值和为45的事实，而每行、每列和每对角线恰好包含三个数，所以每组的和为45除以3即15。因此，检查这些和是否为15是确定一个3x3子矩阵是否为幻方的关键验证步骤。
虽然暴力搜索可能不是效率最高的方法，但它简单直观，易于实现，特别是在处理小规模问题时。对于3x3幻方的检测，考虑到矩阵规模通常不大，暴力搜索可以在可接受的时间内遍历所有可能的3x3子矩阵，并进行幻方验证。这种方法虽然在理论上的时间复杂度较高，但在实际应用中，特别是在LeetCode等在线编程平台的问题中，它通常足够快，能够在规定时间内得到解决。