LeetCode 442. 数组中重复的数据
题目描述
题意分析
数组长度为
n，每个数都在[1, n]内，且每个数只出现一次或两次，返回所有出现两次的值。要求线性时间，并且除返回结果外只使用常数额外空间。值域恰好能映射到数组下标：正整数
x对应位置x - 1。原始元素又全部为正，因此可以把这些位置的正负号当作“是否遇到过某个值”的记录，同时保留绝对值来还原原始数据；这种方法会修改数组符号。
解法：原地符号标记出现状态
核心思路
[!blue]
数组中的一个位置同时承担两种信息：绝对值保留这个位置原来的数字，符号记录“这个下标对应的值是否已出现”。因此扫描当前位置时，先对读到的数取绝对值得到
x，再去下标x - 1检查出现标记，而不是直接根据当前格子的正负判断x是否重复。若
nums[x - 1]仍为正，说明这是第一次扫描到x，把这个位置变成负数，记录它已经出现。标记只改变符号，不改变绝对值，所以即使这个位置还未被扫描到，之后仍能恢复它原来的数字。若对应位置已经为负，说明前面已经遇到过
x，这次就是重复出现，将x加入答案。此时保持标记为负，不把它再次翻回正数。题目保证每个值至多出现两次，因此每个重复值只会在第二次出现时被加入一次。每处理完一个元素，已经出现过的值都在各自独立的槽位留下负号，未出现值的槽位仍为正。这个对应关系使每次判断都准确，而扫描到的绝对值又不会因为别人的标记而丢失，所以一次遍历即可收集全部重复值。
解题步骤
- 创建结果列表，按原数组位置顺序读取元素。
- 对当前读到的值取绝对值，得到原数
x，计算idx = x - 1。- 若
nums[idx] < 0，将x加入答案。- 否则令
nums[idx] = -nums[idx]，记录第一次出现。- 扫描完成后返回答案；本实现保留修改后的符号，不额外恢复输入。
代码实现
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)$，返回结果不计入额外空间；标记直接写入输入数组。
关键点总结
[!green]
- 值域
[1,n]让数值可以映射到数组下标，是原地标记成立的前提。- 负号只记录“出现过”，绝对值仍保存原始数字。
- 读取当前元素必须先取绝对值，因为该位置可能已经被标记。
- 本解法会修改输入；需要保留输入时可在结束后用一趟扫描恢复。
易错点总结
[!yellow]
- 直接使用
value计算下标：它可能已变成负数，必须先取绝对值。- 忘记减一：数值
n会映射到nums[n]，直接越界。- 用 0 作为标记：会破坏原值，之后无法知道该位置原来表示哪个数字。
- 忽略副作用：算法结束后
nums已被修改，若后续还要使用原数组应先恢复。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 448. 找到所有数组中消失的数字 | 简单 | 同样利用1到n的值域把出现信息标到原数组下标，原题找未出现值，本题找重复到达的位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！