LeetCode 题解工作台
数字小镇中的捣蛋鬼
数字小镇 Digitville 中，存在一个数字列表 nums ，其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次 ，然而，有 两个 顽皮的数字额外多出现了一次，使得列表变得比正常情况下更长。 为了恢复 Digitville 的和平，作为小镇中的名侦探，请你找出这两个顽皮的数字。 返…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以用一个数组 记录每个数字出现的次数。 遍历数组 ，当某个数字出现次数为 时，将其加入答案数组中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
数字小镇 Digitville 中，存在一个数字列表 nums，其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次，然而，有 两个 顽皮的数字额外多出现了一次，使得列表变得比正常情况下更长。
为了恢复 Digitville 的和平，作为小镇中的名侦探，请你找出这两个顽皮的数字。
返回一个长度为 2 的数组，包含这两个数字（顺序任意）。
示例 1：
输入： nums = [0,1,1,0]
输出： [0,1]
解释：
数字 0 和 1 分别在数组中出现了两次。
示例 2：
输入： nums = [0,3,2,1,3,2]
输出： [2,3]
解释:
数字 2 和 3 分别在数组中出现了两次。
示例 3：
输入： nums = [7,1,5,4,3,4,6,0,9,5,8,2]
输出： [4,5]
解释:
数字 4 和 5 分别在数组中出现了两次。
提示：
2 <= n <= 100nums.length == n + 20 <= nums[i] < n- 输入保证
nums中 恰好 包含两个重复的元素。
解题思路
方法一：计数
我们可以用一个数组 记录每个数字出现的次数。
遍历数组 ，当某个数字出现次数为 时，将其加入答案数组中。
遍历结束后，返回答案数组即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
cnt = Counter(nums)
return [x for x, v in cnt.items() if v == 2]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for scanning the array once. Space complexity is O(n) for hash set or frequency array, though the mathematical approach reduces space to O(1). The main trade-off is simplicity versus extra space usage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate recognizes using a hash table for quick duplicate detection.
- question_mark
Candidate attempts in-place or mathematical approaches to reduce space usage.
- question_mark
Candidate carefully handles index ranges to avoid off-by-one errors in the array.
常见陷阱
外企场景- error
Failing to handle all duplicates when scanning, recording only the first repeated number.
- error
Confusing indices with values when constructing frequency arrays.
- error
Attempting sum-based approaches without considering two duplicates, leading to incorrect algebra.
进阶变体
外企场景- arrow_right_alt
Find k repeated numbers instead of two, generalizing the hash scan or frequency array.
- arrow_right_alt
Input may contain numbers outside 0 to n-1 range, requiring mapping to handle duplicates.
- arrow_right_alt
Return duplicates in sorted order, emphasizing order handling on top of detection.