本教程讲解如何在线性时间内找出 0 到 n−1 范围内整数数组中的所有重复元素，严格去重并升序返回；重点解析原地标记法的原理、实现与边界处理，规避排序+嵌套循环导致的重复录入和超时问题。
本教程讲解如何在线性时间内找出 0 到 n−1 范围内整数数组中的所有重复元素，严格去重并升序返回；重点解析原地标记法的原理、实现与边界处理，规避排序+嵌套循环导致的重复录入和超时问题。
在解决“查找数组中重复元素”这类问题时，一个常见误区是先排序再遍历比对——虽然逻辑直观，但会带来两个严重问题：一是时间复杂度退化为 O(N log N)，不满足题目要求的 O(N)；二是重复元素连续出现时（如 [1,1,1]），内层循环会导致同一重复值被多次加入结果列表（如输出 1,1 而非仅 1）。你提供的代码正是如此：arr = [1,1,1] 时，i=0 匹配 j=1 和 j=2，两次添加 1，造成结果重复。
✅ 正确解法应遵循两大约束：
- 时间 O(N)：不能依赖排序或双重循环；
-
空间 O(1) 辅助空间（除返回列表外）：禁止使用
HashSet或额外计数数组。
? 核心思路：利用数组下标与值的映射关系进行原地标记
由于题目限定 arr[i] ∈ [0, N−1]，每个元素值都可作为合法下标。我们可通过修改 arr[arr[i] % n] 的值来标记该数字是否已出现过——例如，将首次访问的 val 对应位置 arr[val] 加上 n（即 arr[val] += n），后续再次遇到 val 时，若发现 arr[val] ≥ 2n，即可判定其为重复元素。
⚠️ 注意：因数组可能含重复值，直接取
arr[k]可能已被修改，故统一用k % n获取原始值（确保下标安全）。
以下是符合要求的完整实现：
import java.util.*;
class Solution {
public static ArrayList<Integer> duplicates(int arr[], int n) {
ArrayList<Integer> result = new ArrayList<>();
final int marker = n; // 用 n 作为增量标记基数
// 第一遍扫描：对每个值 val = arr[i]，标记 arr[val % n] += n
for (int i = 0; i < n; i++) {
int val = arr[i] % n; // 安全取原始值（防已修改）
arr[val] += marker;
}
// 第二遍扫描：检查哪些位置的值 ≥ 2*n → 表示该下标值出现 ≥2 次
for (int i = 0; i < n; i++) {
if (arr[i] >= 2 * marker) {
result.add(i);
}
}
// 若无重复，返回 [-1]
if (result.isEmpty()) {
result.add(-1);
}
return result;
}
}? 关键点解析：
-
为什么加
n？ 因为所有原始值 ∈ [0, n−1]，加n后必然 ≥ n，且arr[i] ≥ 2n是“至少出现两次”的充要条件（一次标记 + 至少一次再访问）； -
为何用
arr[i] % n？ 确保无论arr[i]是否已被修改（如变成n+3），% n总能还原出原始值3，保障下标正确性； -
为何结果天然升序？ 第二遍按
i = 0到n−1遍历下标，添加顺序即数值升序，无需额外排序。
? 注意事项：
- 此方法会修改原数组，若题目要求不可修改，需先复制（但会违反 O(1) 辅助空间约束）；
-
n必须 ≥ 1（题设保证），避免marker为 0 导致标记失效； - 返回前务必检查空结果并填入
-1，否则测试用例失败。
该方案真正实现时间复杂度 O(N)、辅助空间 O(1)，完美契合算法挑战的核心要求——用数学思维替代暴力枚举，在约束中寻找最优路径。
