教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文为 AlgoNote「算法通关手册」系列题解完整解析 0645. 错误的集合 这道标签为「位运算、数组、哈希表、排序」的简单难度题目如何在数组恰好出现「一个数字重复、一个数字丢失」时以数组形式同时返回重复数与丢失数。读完本文你将掌握哈希表频率统计、和与平方和联立方程两种解法并能理解二者在时间复杂度、空间复杂度上的取舍以及边界条件与溢出风险。题目解读与约束集合 $S$ 原本包含从 $1$ 到 $n$ 的连续整数但数据出错后「某一个数字复制成了集合里面另外一个数字的值」导致最终数组 $nums$ 中同时存在一个重复数字和一个丢失数字。题目要求找出重复出现的整数与丢失的整数并按[重复的数字, 丢失的数字]的顺序返回。题目给出的约束与示例与 LeetCode 题目保持一致$2 \le nums.length \le 10^{4}$$1 \le nums[i] \le 10^{4}$示例 1nums [1,2,2,4]输出[2,3]2 重复、3 丢失示例 2nums [1,1]输出[1,2]1 重复、2 丢失。关键前提是数组中恰好只存在一个重复数字与一个丢失数字这一前提是所有解法的逻辑基础。本仓库在 00_preface/00_06_categories_list.md 中将该题归入「位运算、数组、哈希表、排序」标签下文将围绕其中最容易上手的两种经典思路展开。思路 1哈希表统计频率最直观的做法是借助哈希表记录每个数字出现的次数然后扫描 $1$ 到 $n$ 即可同时定位重复与丢失。算法步骤使用哈希表freq记录数组中每个数字出现的次数遍历 $i$ 从 $1$ 到 $n$若freq[i] 2说明 $i$ 是重复的数字若freq[i] 0说明 $i$ 是丢失的数字返回[duplicate, missing]。由于数组中只有唯一一个数字出现两次、唯一一个数字未出现因此上述两个条件各命中一次逻辑上不会冲突。参考代码原题解中的完整实现如下class Solution: def findErrorNums(self, nums: List[int]) - List[int]: from collections import Counter n len(nums) freq Counter(nums) duplicate, missing 0, 0 for i in range(1, n 1): if freq[i] 2: duplicate i elif freq[i] 0: missing i return [duplicate, missing]实现要点说明使用collections.Counter(nums)一次性完成频率统计统计后freq[i]默认返回0未出现过的键因此freq[i] 0的判断可以安全命中丢失数字若不想依赖Counter也可手写freq {}并遍历nums累加或使用长度为 $n 1$ 的普通数组作为计数表效果等价本仓库 0268. 丢失的数字 的思路 1 也采用了同一「哈希表 范围扫描」模式可以对照阅读体会该范式在「找缺失」类题目中的通用性。复杂度分析时间复杂度$O(n)$。统计频率遍历数组一次 $O(n)$扫描 $1$ 到 $n$ 一次 $O(n)$合计 $O(n)$空间复杂度$O(n)$。哈希表最多存储 $n$ 个键值对。思路 2数学方法和 平方和联立方程哈希表思路直观但空间开销为 $O(n)$。若能接受纯数学推导则可在 $O(1)$ 空间内求解适合对空间有要求的场景。推导过程设重复的数字为 $x$丢失的数字为 $y$。定义$sum_nums$数组 $nums$ 的元素和$sum_n$$1 2 \cdots n \dfrac{n(n1)}{2}$$sum_sq_nums$数组元素的平方和$sum_sq_n$$1^2 2^2 \cdots n^2 \dfrac{n(n1)(2n1)}{6}$。由于数组中 $y$ 被 $x$ 替换可以建立两个方程一次方程$sum_nums - sum_n x - y$二次方程$sum_sq_nums - sum_sq_n x^2 - y^2 (x y)(x - y)$。令diff sum_nums - sum_n则由两式相除可得$$x y \frac{sum_sq_nums - sum_sq_n}{diff}$$联立一次方程最终解得$$x \frac{diff (x y)}{2}, \qquad y (x y) - x$$参考代码class Solution: def findErrorNums(self, nums: List[int]) - List[int]: n len(nums) # 计算数组的和与平方和 sum_nums sum(nums) sum_sq_nums sum(x * x for x in nums) # 计算 1 到 n 的和与平方和 sum_n n * (n 1) // 2 sum_sq_n n * (n 1) * (2 * n 1) // 6 # x - y sum_nums - sum_n diff sum_nums - sum_n # x^2 - y^2 sum_sq_nums - sum_sq_n # (x y)(x - y) sum_sq_nums - sum_sq_n # x y (sum_sq_nums - sum_sq_n) / (x - y) sum_xy (sum_sq_nums - sum_sq_n) // diff # 求解 x 和 y duplicate (diff sum_xy) // 2 missing sum_xy - duplicate return [duplicate, missing]边界与细节验证用示例 1 手动验证nums [1,2,2,4]$n 4$$sum_nums 9$$sum_sq_nums 14416 25$$sum_n 10$$sum_sq_n 30$。于是diff -1sum_xy (25 - 30) // (-1) 5duplicate (-1 5) // 2 2missing 5 - 2 3输出[2, 3]正确。几个需要留意的实现细节diff不会为 0因为 $x \ne y$重复数与丢失数不可能相同所以 $x - y diff \ne 0$除法安全但若题目描述改为允许其他异常形态则需额外判零负数的整除diff可能为负数如示例 1Python 中//对负数的整除结果仍能保证(x y)(x - y) // (x - y) x y的代数关系成立这是该实现可直接使用//的原因整数溢出$n$ 最大为 $10^{4}$平方和上限约为 $\frac{10^{4} \times 10^{4} \times 2 \times 10^{4}}{6} \approx 3.3 \times 10^{11}$Python 整数无上限无需担心但若用 C/C/Java 等固定位宽语言实现sum_sq需要选用long longC/C或longJava等足够宽的整数类型这是该思路在工程实现中的常见坑点。复杂度分析时间复杂度$O(n)$。仅需遍历数组一次计算和与平方和空间复杂度$O(1)$。只使用了常数级别的额外空间。两思路对比与选型建议解法时间复杂度空间复杂度核心思想适用场景哈希表Counter$O(n)$$O(n)$频率统计 范围扫描思路直观、代码易读适合作为首选写法数学方法和 平方和$O(n)$$O(1)$建立两个方程联立求解对空间敏感、面试中体现推导能力的进阶写法两者时间复杂度相同差异仅在空间常数与代码可读性上。实际刷题或面试时建议先给出哈希表解法保证正确性再补充数学解法的推导过程展示思路深度若被追问「能否不用额外空间」数学方法即为标准答案。扩展从本仓库看同类题目的解题脉络该题与本仓库其他题解构成清晰的「找缺失 / 找重复」知识链建议串读0268. 丢失的数字单一缺失场景同样给出「哈希表」与「数学求和」两种思路其中求和法正是本题思路 2 的一元简化版0287. 寻找重复数单一重复场景给出二分查找解法可对比「仅找重复」与「重复 缺失」问题的不同切入点07_algorithm/07_06_bit_operation.md系统讲解按位与、按位或、按位异或等基础位运算。本题标签包含「位运算」经典做法是把数组全部元素与 $1$ 到 $n$ 全部异或得到 $x \oplus y$再按最低不同位分组异或解出 $x$、$y$可在掌握位运算基础后自行推导实现作为第三种 $O(1)$ 空间的补充练习。此外该题在仓库中的位置为 docs/solutions/0600-0699/set-mismatch.md对应章节索引见 docs/solutions/0600-0699/index.md全量题目清单见 00_preface/00_05_solutions_list.md便于按编号索引检索。小结本题虽标注「简单」却同时覆盖了哈希表、数学推导、位运算三类高频算法思想是练习「数组 数学」类问题的高性价比题目。核心要点可归纳为哈希表思路靠「出现次数为 2 / 0」一箭双雕地定位重复与缺失代码最稳数学思路通过一次方程与二次方程联立求解 $x$、$y$空间最优但需注意整除符号与溢出问题三类标签位运算、数组、哈希表、排序对应至少四种可行解法掌握任意两种即可从容应对面试追问。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解精讲645. Set Mismatch集合错位计数数组解法LeetCode Go 题解精讲645. Set Mismatch集合错位计数数组解法 导读 本文基于 LeetCode Go https://link.示例工程codeforces-go 题解剖析力扣双周赛 176 Q2「前缀连通组」哈希表计数解法codeforces go 题解剖析力扣双周赛 176 Q2「前缀连通组」哈希表计数解法 导读 本题是力扣双周赛 176 的第二题Number of Pre科学计算codeforces-go 仓库实战力扣双周赛 165 Q1 最小缺席正整数——下界枚举 哈希集合的 O(n) 解法codeforces go 仓库实战力扣双周赛 165 Q1 最小缺席正整数——下界枚举 哈希集合的 O n 解法 本篇技术指南以算法竞赛模板库 co科学计算上一篇OpenTracks核心功能详解从轨迹记录到数据统计的完整攻略下一篇Voyager会话存储优化提升并发用户访问体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
