442. Find All Duplicates in an Array

🟠   🔖  数组 哈希表  🔗 LeetCode

题目

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice , return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]

Output: [2,3]

Example 2:

Input: nums = [1,1,2]

Output: [1]

Example 3:

Input: nums = [1]

Output: []

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

题目大意

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

解题思路

题目要求在不使用额外空间和时间复杂度 O(n) 的情况下解决问题。由于 1 <= nums[i] <= n，可以通过修改原数组的方式来标记出现过的元素。

具体的步骤如下：

1. 遍历数组，对于每个元素 nums[i]，将其对应的索引处的元素取反。
2. 当访问到某个元素 nums[j] 时，如果 nums[j] 已经是负数，说明之前已经访问过，表示 j+1 是重复出现的元素。
3. 将找到的重复元素添加到结果数组中。

• 时间复杂度：O(n)，其中 n 是数组的长度。遍历数组一次。
• 空间复杂度：O(1)，不使用额外的空间。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
	let res = [];
	for (let i in nums) {
		const index = Math.abs(nums[i]) - 1;
		if (nums[index] < 0) {
			res.push(index + 1);
		} else {
			nums[index] = -nums[index];
		}
	}
	return res;
};

相关题目

相关题目

• 448. 找到所有数组中消失的数字
• 2615. 等值距离和

- [448. 找到所有数组中消失的数字](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array)
- [2615. 等值距离和](https://leetcode.com/problems/sum-of-distances)