本文介绍如何在 o(n) 时间复杂度、仅用返回列表的额外空间前提下，找出 0 到 n−1 范围内整数数组中的所有重复元素，并避免结果中出现重复数值。核心在于利用数组索引与值的映射关系进行原地标记。
本文介绍如何在 o(n) 时间复杂度、仅用返回列表的额外空间前提下，找出 0 到 n−1 范围内整数数组中的所有重复元素，并避免结果中出现重复数值。核心在于利用数组索引与值的映射关系进行原地标记。
在解决“查找数组中重复元素”问题时，许多初学者会本能地选择先排序再遍历比较（如双层循环或相邻扫描），但这种方法存在两个关键缺陷：
- 时间超标：排序本身为 O(N log N)，不满足题目要求的 O(N)；
-
结果去重缺失：即使排序后扫描，若仅判断
arr[i] == arr[j]，仍可能将同一重复值多次加入结果（例如25出现 3 次，会被添加 2 次甚至更多）。
你提供的代码正是如此：
for(int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if(arr[i]==arr[j]) {
list1.add(arr[i]); // ❌ 同一重复值被反复添加
}
}
}该逻辑未做“首次发现即记录”的控制，导致 25 在匹配 (i=2, j=13)、(i=2, j=22)、(i=13, j=22) 等多组位置时被重复插入。
✅ 正确解法：原地哈希标记（O(N) 时间 + O(1) 额外空间）
题目约束明确指出：“额外空间仅用于返回列表”，且数组元素范围为 [0, N−1] —— 这是典型的原地哈希（in-place hashing） 适用场景。我们可将数组本身作为哈希表，利用 arr[i] % n 提取原始值，并通过累加 n 的倍数来标记“该值是否已出现过”。
? 核心思想：
- 数组中每个合法值
v ∈ [0, N−1]都能唯一对应一个索引v； - 初始时
arr[v] ，我们约定：若 <code>arr[v] ≥ 2n，则表示值v至少出现 2 次； - 遍历原数组，对每个
arr[i]，计算其真实值val = arr[i] % n，然后执行arr[val] += n； - 第二遍扫描
arr[0..n−1]，若arr[i] >= 2*n，说明值i出现 ≥2 次 → 加入结果。
✅ 完整实现（符合 GFG 要求）：
import java.util.*;
class Solution {
public static ArrayList<Integer> duplicates(int arr[], int n) {
ArrayList<Integer> result = new ArrayList<>();
final int MARK_THRESHOLD = 2 * n; // 标记重复的阈值
// 第一遍：利用模运算提取原始值，累加 n 实现计数标记
for (int i = 0; i < n; i++) {
int val = arr[i] % n; // 获取原始值（防越界干扰）
arr[val] += n; // 在对应索引处累加 n
}
// 第二遍：检查哪些索引位置的值 ≥ 2n → 表示该索引值重复
for (int i = 0; i < n; i++) {
if (arr[i] >= MARK_THRESHOLD) {
result.add(i);
}
}
// 若无重复，返回 [-1]
if (result.isEmpty()) {
result.add(-1);
}
return result;
}
}⚠️ 注意事项：
-
不要修改原始值语义：每次访问
arr[i]前必须用% n取模，因为后续元素可能已被标记（如arr[i] = original + k*n）； - *阈值设为 `2n
**：因初始值最大为n−1，一次标记后最大为(n−1)+n = 2n−1，故≥2n` 才能确保至少被标记两次； - 无需排序，无需额外哈希结构：完全满足题目对时间（O(N)）和空间（O(1) 辅助空间）的严苛要求；
-
结果天然有序：因按索引
0→n−1扫描，result中元素自动升序排列，符合题目“ascending order”要求。
? 示例验证（输入 n=26, arr = [13,9,25,...]）：
- 值
1对应索引1，最终arr[1] ≥ 52→ 加入1； - 值
25对应索引25，arr[25] ≥ 52→ 加入25； - 其他重复值同理；
- 无遗漏、无重复、无排序开销 —— 输出精准为
1 3 11 13 14 20 22 25。
该方法不仅高效鲁棒，更是理解“数组即哈希表”这一经典技巧的绝佳范例。掌握它，将为你解决同类原地算法题（如缺失数字、重复数字 II/III）打下坚实基础。
