3212.统计 X 和 Y 频数相等的子矩阵数量：前缀和

【LetMeFly】3212.统计 X 和 Y 频数相等的子矩阵数量：前缀和

力扣题目链接：https://leetcode.cn/problems/count-submatrices-with-equal-frequency-of-x-and-y/

给你一个二维字符矩阵 grid，其中 grid[i][j] 可能是 'X'、'Y' 或 '.'，返回满足以下条件的子矩阵数量：

• 包含 grid[0][0]
• 'X' 和 'Y' 的频数相等。
• 至少包含一个 'X'。

 

示例 1：

输入： grid = [["X","Y","."],["Y",".","."]]

输出： 3

解释：

示例 2：

输入： grid = [["X","X"],["X","Y"]]

输出： 0

解释：

不存在满足 'X' 和 'Y' 频数相等的子矩阵。

示例 3：

输入： grid = [[".","."],[".","."]]

输出： 0

解释：

不存在满足至少包含一个 'X' 的子矩阵。

 

提示：

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] 可能是 'X'、'Y' 或 '.'.

前置注意事项：本题的子矩阵是必须包含左上角的矩阵。

解题方法：前缀和

类似昨天的每日一题3070.元素和小于等于 k 的子矩阵的数目，使用一个$diff$数组存储从$(0,0)$到$(i,j)$的X - Y的数量，再额外使用一个数组存储从$(0,0)$到$(i,j)$是否存在X(或Y)。

遍历过程中维护并更新这两个数组即可。

• 时间复杂度$O(mn)$
• 空间复杂度$O(mn)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-19 22:19:31
 */
class Solution {
private:
    inline int v(int x) {
        return x == 'X' ? 1 : x == 'Y' ? -1 : 0;
    }
public:
    int numberOfSubmatrices(vector<vector<char>>& grid) {
        int ans = 0;
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> hasX(n, vector<bool>(m));  // has x or y
        vector<vector<int>> diff(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i && j) {
                    hasX[i][j] = hasX[i - 1][j] | hasX[i][j - 1] | (grid[i][j] != '.');
                    diff[i][j] = diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1] + v(grid[i][j]);
                } else if (i) {
                    hasX[i][j] = hasX[i - 1][j] | (grid[i][j] != '.');
                    diff[i][j] = diff[i - 1][j] + v(grid[i][j]);
                } else if (j) {
                    hasX[i][j] = hasX[i][j - 1] | (grid[i][j] != '.');
                    diff[i][j] = diff[i][j - 1] + v(grid[i][j]);
                } else {
                    hasX[i][j] = grid[i][j] != '.';
                    diff[i][j] = v(grid[i][j]);
                }
                ans += (!diff[i][j] && hasX[i][j]);
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源