先说结论：力扣第36题“有效的数独”是一道被很多人低估了的好题。表面上是让你检查一个已经填好的数独盘面合不合法，看起来就是三个循环的事，但真正动手写的时候，不少人会在“怎么同时检查行、列、3x3宫格”这个点上卡住，或者写完一个能跑但很冗余的版本。这篇文章就是我整理这道题的完整刷题笔记，从暴力解讲到一次遍历的高效写法，把宫格索引的推导、字符转数字的细节、常见提交错误都拆开说清楚，适合刚接触哈希集合的初学者，也适合准备面试想快速过一遍经典题型的同学。
1. 先把题目看透：这题到底在考什么
1.1 三个条件缺一不可
有效的数独需要满足三条规则：每一行里数字1到9不能重复，每一列里数字1到9不能重复，每一个3x3的宫格里数字1到9也不能重复。注意这里说的“不能重复”是相对已经填进去的数字而言的，空位用“.”表示，不需要你去填数字，也不管这个空位应该填什么。
很多人第一反应是：这不就是三个for循环嵌套吗？确实，最直接的暴力写法就是先遍历每一行，用哈希集合记录出现过哪些数字，遇到重复就返回false；再遍历每一列，做同样的事；最后遍历每一个3x3宫格。这个思路完全正确，但是代码会显得啰嗦，而且三个独立的遍历会让重复逻辑出现三次，面试时写出来很难拿高分。
1.2 最容易跑偏的理解：不是判断“可解的题”
我见过不少朋友看到“数独”两个字，下意识以为这题要判断这个九宫格到底有没有解。这是个大坑。判断有没有解属于另一道题，通常需要回溯算法，从第一个空格开始尝试填数字，填到冲突就回退，非常耗时。而这道题只要求检查“当前已经出现的数字是否违反数独规则”，完全不需要推理。
如果题目要求的是“判断是否可以填充为完整数独”，那么即使当前盘面合法，也可能因为初始数字的布局导致无解。遇到那种情况，你必须在检查规则之后再跑一遍回溯搜索。这道题不做这一步，所以别自己给自己加戏，老老实实完成规则检查就够了。
1.3 为什么这道题值得反复琢磨
从刷题的角度看，这道题的难度评级只是简单，但它的价值在于让你理解一个常见的空间换时间套路：用多个布尔数组或者哈希集合，在一次双重循环里同时维护行、列、宫三种维度的状态。这个套路不止这一题用，后面遇到“单词是否能由字符矩阵拼出”“数图是否有重复”“扑克牌排列是否有效”这类需要多维度去重校验的题目，思路都是相通的。
我自己带过几次刷题小组，发现很多同学做完这题就急着跳到下一道，反而错过了最该消化的部分。它最大的教学点不是怎么解，而是怎么把三个重复的检查合并成一个，以及如何把一个二维坐标映射到九宫格的编号上。后者一旦想明白，很多网格类题目的解法都会变得顺畅起来。
2. 从暴力解到优雅解：三种实现思路对比
2.1 方案一：三轮独立遍历，先别嫌它笨
我建议第一遍自己写的时候，不要一上来就优化，先把暴力版本写出来。思路非常直白：检查每一行有没有重复数字，检查每一列有没有重复数字，检查每一个3x3宫格有没有重复数字。每轮都用集合记录数字，遇到重复就返回false。
class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: # 检查行 for i in range(9): seen = set() for j in range(9): if board[i][j] != '.': if board[i][j] in seen: return False seen.add(board[i][j]) # 检查列 for j in range(9): seen = set() for i in range(9): if board[i][j] != '.': if board[i][j] in seen: return False seen.add(board[i][j]) # 检查 3x3 宫格 for box in range(9): seen = set() # 每个宫格的左上角坐标 start_row = (box // 3) * 3 start_col = (box % 3) * 3 for i in range(start_row, start_row + 3): for j in range(start_col, start_col + 3): if board[i][j] != '.': if board[i][j] in seen: return False seen.add(board[i][j]) return True这个版本时间复杂度是O(1)，因为盘面固定是9x9，循环次数恒定为81，但是代码量偏多，而且你会发现“检查行”和“检查列”的结构完全一样，只是i和j调换了位置，这给后面合并检查埋下了伏笔。写这个版本的价值在于，它帮你把题目要求完整地翻译成代码，理清楚三大检查是什么。
2.2 方案二：一次遍历+哈希集合，用标识串合并三次检查
既然行、列、宫都要检查重复，能不能在遍历每个格子的时候，同时把三类检查一起做了？答案是可以。关键在于给每个“检查维度”设计一个唯一的标识。
比如对于第3行、数字5，可以用标识串"row-3-5"；对于第4列、数字7，用"col-4-7"；对于第2个宫格、数字6，用"box-2-6"。遍历到任何一个数字时，我们把三类标识都放进同一个哈希集合。如果在放入之前发现某个标识已经存在于集合中，说明这一行、这一列或者这个宫格里已经有相同的数字了，直接返回false。
class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: seen = set() for i in range(9): for j in range(9): c = board[i][j] if c == '.': continue box_index = (i // 3) * 3 + j // 3 row_key = f"row-{i}-{c}" col_key = f"col-{j}-{c}" box_key = f"box-{box_index}-{c}" if row_key in seen or col_key in seen or box_key in seen: return False seen.add(row_key) seen.add(col_key) seen.add(box_key) return True这个写法的优点是逻辑清晰，一个循环解决全部问题，面试时容易解释。缺点是字符串拼接会带来少量额外开销，而且哈希集合存储的是字符串，理论上内存使用比纯布尔数组要大一些。不过对于固定81格的输入，这点差异完全可以忽略。
2.3 方案三：布尔数组+宫格索引公式，把内存再压一层
如果你对性能有执念，或者面试官追问“能不能不用字符串”，可以用三个二维布尔数组代替哈希集合。rows[i][num]表示第i行是否出现过数字num，cols[j][num]表示第j列是否出现过数字num，boxes[box][num]表示第box个宫格是否出现过数字num。这里num要用0到8的整数表示数字1到9，也就是把字符转成数字后再减1。
class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: rows = [[False] * 9 for _ in range(9)] cols = [[False] * 9 for _ in range(9)] boxes = [[False] * 9 for _ in range(9)] for i in range(9): for j in range(9): if board[i][j] == '.': continue num = int(board[i][j]) - 1 box_index = (i // 3) * 3 + j // 3 if rows[i][num] or cols[j][num] or boxes[box_index][num]: return False rows[i][num] = True cols[j][num] = True boxes[box_index][num] = True return True三种方案里，我个人最推荐最后这个写法。它没有字符串拼接，没有哈希冲突，数组访问速度极快，而且能帮助你把数独问题的状态管理方式理解透彻。很多标着“困难的数独变种题”，比如第37题，用的状态标记思路跟这个完全一致。
3. 核心细节解剖：宫格索引与数据结构选型
3.1 3x3宫格索引公式是怎么推出来的
宫格索引box_index = (i // 3) * 3 + j // 3是这道题最经典的公式，很多人直接背下来，但不知道原理。我建议还是自己推一遍，以后遇到变体题不容易翻车。
先看行的方向：盘面总共有9行，每3行组成一个“宫格行”，所以i // 3得到的是0、1、2三档。比如第4行，4 // 3 = 1，说明它位于第二个宫格行。再看列的方向：第j列除以3得到0、1、2三档。把“第几个宫格行”乘以3，再加上“第几列”所在的档位，就是整个9x9盘面里宫格的编号。
举个例子，第5行第7列的格子：i // 3 = 1，j // 3 = 2，所以box_index = 1 * 3 + 2 = 5。你可以手动数一下盘面，从左到右从上到下给9个宫格编号，第5行第7列确实落在编号为5的宫格里。这个公式之所以好用，是因为它把二维平面坐标线性化成了单维编号，这个思想在很多网格题里都适用。
注意：有的教程会把宫格编号写成
(i / 3) * 3 + (j / 3)，在Python单斜杠是浮点除法，必须用双斜杠//取整，否则会得到浮点数，甚至直接导致下标越界。我见过不少人在本地跑得好好的，提交却报错，查了半天发现是除号写错了。
3.2 字符转数组下标，一个容易翻车的细节
用布尔数组方案时，不能直接把字符'5'塞进数组当下标，必须先转成整数再减一。原因是数组大小是9，下标范围是0到8，而字符对应的数字是1到9。int('5') - 1 = 4，表示数字5存在时，把第4个位置标记为true。
有的同学会写成ord(board[i][j]) - ord('0')，这样也能得到整数，不过要记得再减一。还有同学在判断重复时，先比较字符是否等于某个数字，再决定是否跳过，这样虽然也能跑，但逻辑绕了一圈，不如直接int()转换干净。刷题时保持直白的风格，反而更容易检查边界。
字符'.'的处理也要注意。空位不参与规则检查，所以在读取board[i][j]之后，第一步先判断是不是'.'，如果是就直接continue。千万不要把点号当成某个数字去转换，否则int('.')会直接抛异常。
3.3 HashSet和布尔数组到底怎么选
面试时如果时间紧张，写HashSet方案最稳妥，因为它逻辑直观，不容易出现下标错误，并且代码量少。如果面试官追问优化空间，你再拿出布尔数组方案展示自己理解底层差异。
从纯技术角度看，布尔数组方案的时间效率和空间效率都优于HashSet。数组是连续内存，访问O(1)而且常数极小；HashSet底层是哈希表，虽然也是O(1)平均复杂度，但计算哈希、处理可能的冲突都要花时间。固定只有81个格子的场景下两者差距不大，但涉及更大规模的多维去重问题时，数组方案的优势会明显放大。
另外提一句位运算思路：有人会用int的二进制位来标记数字是否出现，9个数字用9个bit就够了。这样可以进一步把三个二维数组压缩成三个一维整数数组，甚至三个整数变量，但这属于炫技写法，面试时解释成本高，日常工程里可读性也差。我建议把它当作拓展思路看看就好，不用作为主推方案。
4. 复杂度分析与同类题型延伸
4.1 为什么优化了半天，复杂度还是O(1)
这道题最容易被忽略的点是：它的输入规模是固定的9x9，不存在“n趋近无穷大”的情况。所以整个双层循环的执行次数恒定就是81次，时间复杂度是O(1)，空间复杂度也是O(1)。正是因为输入固定，这道题任何“优化”在绝对复杂度上都不会产生量级变化，优化更多体现在常数因子和代码可读性上。
有些同学会疑惑：既然复杂度都一样，是不是随便写个暴力版本就行？从通过题目的角度确实可以，但从面试考察的角度不行。面试官想看你能否在限定条件下写出简洁、少重复的代码，以及是否理解哈希集合和数组在不同场景下的取舍。拿暴力版本硬扛，哪怕能过题，也很容易被追问“可不可以只遍历一次”，到时候被问住了反而扣分。
4.2 顺藤摸瓜：这道题跟解数独的关系
力扣第37题叫“解数独”，核心是让你填充空格，使整个盘面满足有效数独的条件。很多人做了第36题再去做第37题，会惊讶地发现第36题的检查逻辑刚好可以作为回溯算法的剪枝条件。
回溯求解时，你每尝试填一个数字，都需要判断当前盘面是否仍然有效。如果每次都从头遍历整个盘面做校验，耗时会很夸张。更常见的方法是在填入数字的瞬间，立刻更新行、列、宫的状态标记，如果发现冲突就撤销这个选择。这就是所谓的“增量检查”。
这时候你在第36题里写的布尔数组逻辑完全可以直接迁移过来。我把这个关联写出来，是希望大家别把每道题当孤岛，很多中等难度和困难题所谓的新颖点，背后都是简单题里已经出现过的状态管理思路。
4.3 变体玩法：如果题目改成“判断可否完成”怎么办
如果把题目改成“这个初始盘面能否通过填充空格形成一个完整的有效数独”，那么单纯检查当前规则就不够了。你需要回溯算法，核心流程是：先定位一个空格，依次尝试填1到9，每填一个数字都校验是否合法，合法就进入下一个空格，如果所有数字都填不进去，就回退到上一步重新尝试。
性能优化的关键在于填数的顺序，通常优先尝试“候选数字最少”的空格，这样能快速剪枝，避免无意义的搜索。候选数字就是当前空格所在行、列、宫都已经出现过的数字的补集。到这里，第36题里的行、列、宫三种状态标记又从“题目本身”变成了“算法工具”，再一次体现了它的基础性。
这类变体问题在实际工程里也很常见，比如排课系统要判断给定的课表有没有冲突，本质上就是“多个维度不能重复”的校验，只不过维度不是行、列、宫，而是时间、教室、教师。理解了这层抽象，你会发现自己练的不仅是算法，还是一种通用的冲突检测模型。
5. 真实提交避坑记录：我踩过的五个典型错误
5.1 错误一：boxIndex行列算反
我最早写这道题时，把宫格索引写成(j // 3) * 3 + i // 3，提交之后样例直接失败。原因很简单，我把行列顺序搞反了，导致虽然遍历了所有格子，但进入第几个宫格完全对不上，同一个宫格里的数字被分散到了不同的box编号里，根本无法正确查重。这个错误非常隐蔽，因为编译不会报错，代码逻辑看起来也通顺，只有结果不对。
排查技巧是：遇到宫格相关错误，先手动算三到四个网格点，比如(0, 0)对应box 0，(2, 2)对应box 0，(3, 3)对应box 4，(8, 8)对应box 8。把这些基准点代进公式验证，很快就能发现公式写反了。
5.2 错误二：把'.'当成有效数字处理
这个错误在HashSet方案里最容易犯。如果你遍历到'.'之后直接生成"row-0-."这样的标识，那么多个空位会被当成同一个数字，导致合法的盘面被判成非法。所有写法里都必须先判断当前格子是不是'.'，是就跳过。
有些同学喜欢用if board[i][j] != '.'这样的条件包住后续逻辑，这没问题。但要注意缩进和括号匹配，别把continue写在了循环外面，否则又会变成空位也进入统计流程。
5.3 错误三：数组下标从1开始，边界越界
用布尔数组版本时，有人会把int(board[i][j])直接当作下标，也就是数字5对应第5个位置。因为数组初始化成[False] * 9只有9个位置，下标范围是0到8，直接用数字5作为下标访问的是第5个位置，确实不越界，但数字9作为下标就会越界。
正确的映射是下标=数字-1，数字1到9分别对应0到8。这样做的好处是数组刚好9个位置全部利用，不会浪费第一个位置，也不会有越界风险。写完后可以自查：数组长度是9，my下标取值必须都在0到8之间。
5.4 错误四：想用对角线偷懒
有几个兄弟脑洞比较大，觉得既然行、列都有9个，可以只检查主对角线上的格子，或者用两个对角线来覆盖所有行列关系。这个思路方向就错了。对角线上只有9个格子，无法覆盖全部81个格子，更别提宫格检查。任何“只检查一部分格子”的思路都无法通过题目的全部测试用例。
正确的原则是：行、列、宫三条检查线必须是全量的，任何一个数字都不能漏掉。想用更少代码没问题，但前提是覆盖范围不能缩水。
5.5 错误五：暴力法只查行和列，忘了宫格
第一遍实现暴力法时，我写着写着就只检查了行和列，觉得宫格反正也是由行列派生出来的，应该不会有问题。实际上这是错觉。一个盘面完全可能存在“每一行和每一列都无重复，但某个宫格里有两个相同数字”的情况。道理很简单，宫格的划分和行列并不对齐，两个数字可以分居不同行不同列，却挤在同一个宫格里。
这个教训我很想说给所有初学者听：不要凭直觉省略条件，数独的三个约束是相互独立的，必须都检查。宁可代码多写几行，也不要用错误假设挑战测试数据。
6. 刷题策略与个人体会
6.1 这类“状态标记”题的通用解法套路
做完第36题后，我总结出一套处理“多维去重校验”的通用步骤。先枚举所有可能参与重复检查的维度，看它们是独立的还是组合的。然后为每个维度设计唯一标识，标识可以是字符串“维度名+编号+元素值”，也可以是数组里的一个“维度+下标”位置。最后在遍历过程中尝试把标识写进集合或数组，遇到已存在的标识就判定非法。
这套套路几乎是模板级别的，特别适合面试现场快速理清思路。很多同学在遇到题目时容易慌，其实就是因为没有把重复出现的逻辑抽象成统一模型。你可以拿这道题当磨刀石，先把套路练熟，再去做其他网格类题目。
6.2 面试时怎么表现这道题
这道题在面试中出现的频率不低，因为它足够经典，而且讨论空间很大。面试时建议先给对方讲清你的核心思路：用一套遍历同时检查行、列、宫，然后解释宫格索引公式。如果对方表现出兴趣，再补充布尔数组相比HashSet在性能上的区别。
复盘的时候可以再提一个点：由于盘面大小固定，复杂度可以视为O(1)，但如果把这套逻辑推广到任意N x N，那么时间和空间复杂度都会变成O(N^2)，并且需要保证N是3的倍数。这能体现出你不只会背题，还能理解题目背后的推广意义。
6.3 一些刷题顺序建议
如果你刚开始刷题，我建议不要急着做困难题，先用“有效数独”这类题建立状态标记的直觉。刷完第36题后，按顺序可以做第37题解数独，加深对状态标记在回溯中应用的理解。然后再回头刷一些二维字符矩阵类的题，比如“单词搜索”，你会发现它们都建立在类似的坐标遍历和去重逻辑之上。
我个人还会在刷完一道题之后，把这道题的“关键变量”记在一个文档里，比如宫格索引公式、字符转数字映射、边界条件。不是为了背题，而是为了下次遇到相似题目时快速检索，节省重新推导的时间。这个习惯帮我后期刷题效率提升了不少。
最后再分享一个小技巧：这题提交通过不算完，尝试在本地把HashSet方案和布尔数组方案都写一遍，分别跑同一个输入，比较两者的耗时和代码风格。不要只停在“能过”的层次上，多一步“哪种写法表达得更好”的思考，往往才是刷题提升的拐点。
