这道题是经典的数组原地哈希问题，非常适合用来练习 O(1) 空间复杂度的技巧。
题目简述
给定一个长度为 n 的整数数组 nums，其中所有整数都在范围 [1, n] 内，且每个整数出现 一次或两次。请找出所有出现 两次 的整数。
要求：时间复杂度 O(n)，空间复杂度 O(1)（不包括输出数组）。
核心思路
利用数组下标作为哈希表。由于数字范围是 [1, n]，我们可以将数字 x 映射到下标 x – 1。遍历数组时，将对应下标的元素取反作为“已访问”标记。如果某个下标的元素已经是负数，说明对应的数字之前已经出现过，即为重复数据。
Java 实现
import java.util.ArrayList;
import java.util.List;
class Solution {
public List findDuplicates(int[] nums) {
List result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
// 取绝对值，因为之前的操作可能已经将其变为负数
int index = Math.abs(nums[i]) – 1;
// 如果对应位置的数已经是负数，说明之前访问过，即找到了重复
if (nums[index] < 0) {
result.add(Math.abs(nums[i]));
} else {
// 否则，将其标记为已访问（取反）
nums[index] = -nums[index];
}
}
return result;
}
}
复杂度分析
- 时间复杂度：O(n)，只需遍历数组一次。
- 空间复杂度：O(1)，除输出数组外没有使用额外空间。
面试延伸
如果面试官追问其他解法，可以补充：
- 排序法：排序后相邻元素比较，时间 O(n log n)，空间 O(1)。
- HashSet：遍历时判断是否已存在，时间 O(n)，空间 O(n)。
- 交换归位法：将每个数字放到其对应的下标位置，如果目标位置已有正确数字则说明重复。
原地取反法是这类“数字范围在 [1, n]”题目的通用技巧，掌握后可以快速应对类似变体。
需要我接着为你讲解同系列高频面试题 LeetCode 287. 寻找重复数的 Java 实现吗？
