442. 数组中重复的数据
题目描述
输入长度为 n 的整数数组 nums。数组里每个值都在 [1, n] 之间，并且每个值最多出现两次。
找出所有恰好出现了两次的值，放进一个数组返回。没有这样的值时返回空数组。返回顺序不限。
要求算法的时间复杂度为 O(n)，除用来存放答案的数组外只使用常数级额外空间。
示例 1
输入：nums = [4,3,2,7,8,2,3,1] 输出：[2,3]
解释：2 和 3 各出现两次。
示例 2
输入：nums = [1,1,2] 输出：[1]
解释：只有 1 出现两次。
示例 3
输入：nums = [1] 输出：[]
解释：唯一的元素只出现一次，返回空数组。
数据范围
n == nums.length1 <= n <= 10^51 <= nums[i] <= nnums中每个值出现一次或两次。
解题思路：正负号标记
值域恰好是 [1, n]，于是可以把数组本身当作哈希表：数字 v 对应下标 v-1 这个格子。读到 x 时看格子 nums[|x|-1] 的符号：正数说明 |x| 第一次出现，把它改成负数留下“来过”的记号；已经是负数说明 |x| 之前出现过，它就是重复的数。读数时要取绝对值，因为当前格子可能已经被别的数翻成负号。
为什么正确
处理完前若干个数后，nums[v-1] < 0 当且仅当 v 已经在这些数中出现过；ans 恰好是已出现两次的数。
复杂度分析
时间 O(n)，额外空间 O(1)（不计返回数组）。
易错点
计算下标时忘记取绝对值：当前读到的数可能已经被改成负数，直接用 x-1 会得到负下标。加入答案时同样要用 abs(x)。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
ans = []
for x in nums:
i = abs(x) - 1
if nums[i] < 0:
ans.append(abs(x))
else:
nums[i] = -nums[i]
return ansclass Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();
for (int x : nums) {
int i = Math.abs(x) - 1;
if (nums[i] < 0) {
ans.add(Math.abs(x));
} else {
nums[i] = -nums[i];
}
}
return ans;
}
}class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ans;
for (int x : nums) {
int i = abs(x) - 1;
if (nums[i] < 0) {
ans.push_back(abs(x));
} else {
nums[i] = -nums[i];
}
}
return ans;
}
};func findDuplicates(nums []int) []int {
ans := []int{}
for _, x := range nums {
if x < 0 {
x = -x
}
i := x - 1
if nums[i] < 0 {
ans = append(ans, x)
} else {
nums[i] = -nums[i]
}
}
return ans
}var findDuplicates = function(nums) {
const ans = [];
for (const x of nums) {
const i = Math.abs(x) - 1;
if (nums[i] < 0) {
ans.push(Math.abs(x));
} else {
nums[i] = -nums[i];
}
}
return ans;
};function findDuplicates(nums: number[]): number[] {
const ans: number[] = [];
for (const x of nums) {
const i = Math.abs(x) - 1;
if (nums[i] < 0) {
ans.push(Math.abs(x));
} else {
nums[i] = -nums[i];
}
}
return ans;
}其他解法
两种方法都把数组本身当哈希表；正负号标记只翻转符号，代码更短；交换归位让每个数回到自己的位置，适用范围更广。
解法 2：原地交换归位 时间 O(n)，空间 O(1)
值域为 1..n，把每个数 x 交换到下标 x−1 上，直到当前位置的数已在正确位置或目标位置已有相同的数。完成后，凡是 nums[i] ≠ i+1 的位置，nums[i] 就是一个重复出现的数。
这是“原地哈希”的通用写法，可以解决缺失数、重复数等一类题。每个数最多被交换一次，但 while 套 for 的结构需要理解均摊分析。
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
n = len(nums)
# 把每个数 x 换到下标 x-1 上
for i in range(n):
while nums[i] != nums[nums[i] - 1]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
return [nums[i] for i in range(n) if nums[i] != i + 1]class Solution {
public List<Integer> findDuplicates(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] != nums[nums[i] - 1]) {
int j = nums[i] - 1;
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) if (nums[i] != i + 1) ans.add(nums[i]);
return ans;
}
}class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
while (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);
}
vector<int> ans;
for (int i = 0; i < n; i++) if (nums[i] != i + 1) ans.push_back(nums[i]);
return ans;
}
};func findDuplicates(nums []int) []int {
n := len(nums)
for i := 0; i < n; i++ {
for nums[i] != nums[nums[i]-1] {
j := nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
}
}
ans := []int{}
for i := 0; i < n; i++ {
if nums[i] != i+1 {
ans = append(ans, nums[i])
}
}
return ans
}var findDuplicates = function(nums) {
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] !== nums[nums[i] - 1]) {
const j = nums[i] - 1;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
const ans = [];
for (let i = 0; i < n; i++) if (nums[i] !== i + 1) ans.push(nums[i]);
return ans;
};function findDuplicates(nums: number[]): number[] {
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] !== nums[nums[i] - 1]) {
const j = nums[i] - 1;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
const ans: number[] = [];
for (let i = 0; i < n; i++) if (nums[i] !== i + 1) ans.push(nums[i]);
return ans;
}