LeetCode 442. 数组中重复的数据
目录
题目描述
题意分析
给定一个长度为 $n$ 的整数数组
nums，题目保证每个元素都落在 $[1, n]$ 这个区间里，其中一部分数字出现了两次，其余数字只出现一次。要求返回所有出现两次的数字，顺序不限。题面里两句约束不是背景描述，而是解法的全部依据。第一句是「值域恰好是 $[1, n]$」：元素能取的值和数组的下标一一对应，数组自己就是一张长度刚好够用的桶。第二句是「每个元素至多出现两次」：这意味着每个数字最多只需要记录一次「我来过」的痕迹，不需要计数器，一个布尔量级的信息就够。
另外要注意进阶要求：时间 $O(n)$、除返回结果外只用常数额外空间。这一条直接封死了排序（$O(n \log n)$）和哈希表（$O(n)$ 额外空间）两条路，等于明示答案必须在原数组内部做文章。
边界方面：数组长度可能为 $1$，此时不可能有重复，返回空列表；也可能完全没有重复元素，同样返回空列表；结果个数最多为 $n / 2$。返回结果所占的空间按惯例不计入空间复杂度。
解法：原地符号标记出现状态
核心思路
问题关键：数组长度为
n，每个数都在[1,n]中，数值x可以天然映射到下标x-1。题目又要求 $O(n)$ 时间和 $O(1)$ 额外空间，因此应复用原数组记录“是否见过”。为什么选符号标记：输入初始全为正数，可以把
nums[x-1]的正负当作数字x的访问标记，同时绝对值仍保留原数据。扫描到数字x时：
nums[x-1] > 0：第一次出现，将其变为负数；nums[x-1] < 0：此前已经出现过，x就是重复数字。不变量与正确性：处理完任意前缀后，
nums[x-1] < 0当且仅当x已在该前缀出现过。第一次遇到x时建立标记，第二次遇到时必然命中标记并加入答案。题目保证每个数字最多出现两次，因此不会重复加入。当前元素所在位置可能已被前面的数字改成负数，所以读取时必须先取绝对值。本解法会修改输入；若调用方要求保留原数组，结束后再统一恢复正数即可。
解题步骤
- 创建结果列表，依次扫描数组。
- 对当前值取绝对值得到
x，计算映射下标idx = x - 1。- 若
nums[idx]已为负，将x加入答案；否则把nums[idx]变为负数。- 扫描结束后返回答案。
以
[4,3,2,7,8,2,3,1]为例，第一次遇到 2 和 3 时已把对应位置变负；再次遇到它们时命中负号，得到[2,3]。
代码实现
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();
for (int value : nums) {
int x = Math.abs(value);
int idx = x - 1;
if (nums[idx] < 0) {
ans.add(x);
} else {
nums[idx] = -nums[idx];
}
}
return ans;
}
}
func findDuplicates(nums []int) []int {
ans := make([]int, 0)
for _, value := range nums {
x := value
if x < 0 {
x = -x
}
idx := x - 1
if nums[idx] < 0 {
ans = append(ans, x)
} else {
nums[idx] = -nums[idx]
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素只处理一次。
- 空间复杂度：$O(1)$，返回结果不计入额外空间；标记直接写入输入数组。
关键点总结
- 值域
[1,n]让数值可以映射到数组下标，是原地标记成立的前提。- 负号只记录“出现过”，绝对值仍保存原始数字。
- 读取当前元素必须先取绝对值，因为该位置可能已经被标记。
- 本解法会修改输入；需要保留输入时可在结束后用一趟扫描恢复。
易错点总结
- 直接使用
value计算下标：它可能已变成负数，必须先取绝对值。- 忘记减一：数值
n会映射到nums[n]，直接越界。- 用 0 作为标记：会破坏原值，之后无法知道该位置原来表示哪个数字。
- 第二次命中后再次翻转符号：会把标记恢复为正数，破坏不变量。
- 忽略副作用：算法结束后
nums已被修改，若后续还要使用原数组应先恢复。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 448. 找到所有数组中消失的数字 | 简单 | 同样的符号标记，收集的是仍为正的下标 |
| 645. 错误的集合 | 简单 | 一次遍历同时定位重复数与缺失数 |
| 287. 寻找重复数 | 中等 | 禁止修改数组，改用快慢指针判圈 |
| 41. 缺失的第一个正数 | 困难 | 值域映射从标记升级为原地置换 |