36. 有效的数独

✨核心逻辑

本题采用 哈希表/布尔数组标记法 的策略：

建立标记数组：由于数独是固定的 9x9 大小，数字也是固定的 1-9。我们可以用 3 个二维布尔数组（模拟哈希集合），分别记录每一行、每一列、以及每一个 3x3 宫格内，数字 1-9 是否已经出现过。
一次遍历填表：遍历整个 9x9 棋盘。每遇到一个非空的数字字符，就计算它对应的行索引、列索引以及宫格索引。
冲突检测：检查对应的标记位是否已经为 true。如果为 true，说明在该行/列/宫格中已经出现过该数字，直接返回 false。
更新状态：如果没有冲突，则分别把对应行、列、宫格的标记位设为 true。
遍历结束：如果完整遍历完 9x9 棋盘都没有发生冲突，说明当前填写的数字是有效的，返回 true。

🔥代码实现（含详细变量注释）

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // rows：记录每一行的数字出现情况。rows[i][num] 表示第 i 行是否出现过数字 num+1
        boolean[][] rows = new boolean[9][9];
        // cols：记录每一列的数字出现情况。cols[j][num] 表示第 j 列是否出现过数字 num+1
        boolean[][] cols = new boolean[9][9];
        // boxes：记录每一个 3x3 宫格的数字出现情况。boxes[box][num] 表示第 box 个宫格是否出现过数字 num+1
        boolean[][] boxes = new boolean[9][9];
        
        // i：行遍历指针，遍历 0 到 8 行
        for (int i = 0; i < 9; i++) {
            // j：列遍历指针，遍历 0 到 8 列
            for (int j = 0; j < 9; j++) {
                // c：当前正在遍历的棋盘字符
                char c = board[i][j];
                // 如果是空格 '.'，说明没有填入数字，跳过当前循环
                if (c == '.') {
                    continue;
                }
                // index：将字符数字转换为对应的数组下标 0~8（例如 '1' -> 0, '9' -> 8）
                int index = c - '1';
                // boxIndex：计算当前格子 (i, j) 对应的是 9 个 3x3 宫格中的哪一个（索引 0~8）
                // 公式推导：i / 3 算出在第几行宫格，3 * (j / 3) 算出在宫格矩阵中的水平偏移量
                int boxIndex = i / 3 + 3 * (j / 3);

                // 冲突检查：判断当前数字是否已经在当前行、当前列、或当前宫格中出现过
                if (rows[i][index] || cols[j][index] || boxes[boxIndex][index]) {
                    return false;
                }
                
                // 如果没冲突，分别把对应的标记位设为 true，表示该数字已出现过
                rows[i][index] = true;
                cols[j][index] = true;
                boxes[boxIndex][index] = true;
            }
        }
        // 遍历完所有格子都没触发冲突，说明数独当前状态有效
        return true;
    }
}

⏱️复杂度分析
- O(1)。虽然有两层嵌套循环，但数独的大小是固定的 9x9（常数 81 格），因此最多只需检查 81 个格子，时间复杂度为常数级别。
- 空间复杂度：O(1)。使用了 3 个大小为 9x9 的布尔数组，总共占据固定大小为 243 的布尔空间，且没有随输入规模增加而增加，空间复杂度为常数级别。