LeetCode 题解工作台
数组中重复的数据
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 最多 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间（不包括存储输出所需的空间）的算法解决此问题。 示例 1…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def findDuplicates(self, nums: List[int]) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 最多两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间（不包括存储输出所需的空间）的算法解决此问题。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1] 输出：[2,3]
示例 2：
输入：nums = [1,1,2] 输出：[1]
示例 3：
输入：nums = [1] 输出：[]
提示：
n == nums.length1 <= n <= 1051 <= nums[i] <= nnums中的每个元素出现 一次 或 两次
解题思路
方法一
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
while nums[i] != nums[nums[i] - 1]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
return [v for i, v in enumerate(nums) if v != i + 1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate an understanding of space optimization while solving the problem.
- question_mark
Look for candidates who can explain trade-offs between hash set and in-place modification techniques.
- question_mark
Assess if the candidate can explain how to meet the O(n) time and constant space requirements.
常见陷阱
外企场景- error
Failing to achieve constant auxiliary space by using extra arrays or hash sets.
- error
Misunderstanding the need for O(n) time complexity, resulting in inefficient solutions.
- error
Incorrectly handling edge cases, such as when the array contains no duplicates.
进阶变体
外企场景- arrow_right_alt
Modify the problem to return only the first duplicate found.
- arrow_right_alt
Alter the constraints to allow for numbers appearing more than twice.
- arrow_right_alt
Ask for the solution to be implemented without modifying the input array.