LeetCode 3212. 统计X和Y出现次数相等的子矩阵数量题目描述给你一个大小为m x n的二维字符矩阵grid矩阵中的每个字符要么是X要么是Y要么是.。请你统计所有以 (0,0) 为左上角、以任意格子为右下角的子矩阵中满足以下条件的个数子矩阵中至少包含一个X子矩阵中X和Y的出现次数相等。示例例如输入grid [[X,Y,.],[Y,.,X]] 输出3 解释以 (0,0) 为左上角的子矩阵中有 3 个满足条件。示例仅为辅助理解具体可参考原题解题思路本题要求统计所有固定左上角为原点的子矩阵因此我们可以利用二维前缀和来快速计算任意从(0,0)到(i,j)的矩形区域内X和Y的数量。算法步骤定义三维数组sum[m1][n1][2]其中sum[i1][j1][0]表示从(0,0)到(i,j)的子矩阵中X的数量sum[i1][j1][1]表示Y的数量。遍历每个格子(i,j)利用容斥原理更新前缀和sum[i1][j1][0] sum[i1][j][0] sum[i][j1][0] - sum[i][j][0]; sum[i1][j1][1] sum[i1][j][1] sum[i][j1][1] - sum[i][j][1];如果当前格子不是.根据字符的最低位增加对应计数X的 ASCII 码为 88二进制1011000最低位 0Y的 ASCII 码为 89二进制1011001最低位 1。因此可以用grid[i][j] 1来区分值为 0 表示X值为 1 表示Y并将相应维度的计数加 1。每次更新完当前(i,j)对应的前缀和后立即检查从(0,0)到(i,j)的矩形是否满足条件sum[i1][j1][0] 0至少一个Xsum[i1][j1][0] sum[i1][j1][1]数量相等。若满足则答案ans加 1。遍历结束返回ans。代码实现classSolution{public:intnumberOfSubmatrices(vectorvectorchargrid){intans0,mgrid.size(),ngrid[0].size();// 三维前缀和sum[i1][j1][0] 表示 (0,0) 到 (i,j) 的 X 数量[1] 表示 Y 数量vectorsum(m1,vectorarrayint,2(n1));for(inti0;im;i){for(intj0;jn;j){// 容斥原理更新前缀和sum[i1][j1][0]sum[i1][j][0]sum[i][j1][0]-sum[i][j][0];sum[i1][j1][1]sum[i1][j][1]sum[i][j1][1]-sum[i][j][1];// 如果当前格子不是 .则根据字符最低位增加对应计数if(grid[i][j]!.){sum[i1][j1][grid[i][j]1];}// 检查从 (0,0) 到 (i,j) 的子矩阵是否满足条件if(sum[i1][j1][0]sum[i1][j1][0]sum[i1][j1][1]){ans;}}}returnans;}};复杂度分析时间复杂度O(m × n)只需遍历矩阵一次每次更新和检查都是 O(1) 操作。空间复杂度O(m × n)用于存储二维前缀和数组。总结本题利用二维前缀和快速获取子矩阵中字符的频次并通过巧妙的位运算区分X和Y代码简洁高效。注意题目要求子矩阵必须从(0,0)开始因此只需枚举右下角即可。