0442. Find All Duplicates in an Array ===================================== 题目信息 -------- :题号: 0442 :难度: Medium :主题: 长度为 ``n`` 的数组、数值范围 ``1..n``、出现两次、重复值集合 :原题: `LeetCode 0442 `_ :重点: 每个值只出现一次或两次、结果只列出现两次的值、顺序不限、要求线性时间和常数额外空间 题目重述 -------- 给定长度为 ``n`` 的整数数组 ``nums``,每个元素都位于 ``[1, n]``,并且每个整数在数组中出现一次或两次。返回所有恰好出现两次的整数。 ``n`` 位于 ``[1, 10^5]``。每个重复值在结果中只出现一次,结果顺序不限。题目要求使用 ``O(n)`` 时间,并且除返回结果外只使用常数额外空间;允许在处理过程中修改输入数组。 自建示例 -------- 存在两个重复值: .. code-block:: text 输入:nums = [1, 3, 4, 2, 2, 3] 输出:[2,3] 解释:2 和 3 各出现两次,1 和 4 各出现一次;输出顺序也可以是 [3,2]。 没有重复值: .. code-block:: text 输入:nums = [1, 2, 3] 输出:[] 解释:每个数都只出现一次,因此结果为空。 用下标位置记录出现次数 ------------------------ 数组值 ``x`` 的合法范围正好对应下标 ``x - 1``。第一次遇到 ``x`` 时,把 ``nums[x - 1]`` 取负作为“已经见过”的标记;再次遇到 ``x`` 时,该位置已经是负数,于是把 ``x`` 加入答案。读取值时先取绝对值,因为此前的标记可能已经改变了它的符号。 这种做法利用了题目允许修改输入数组的条件,不需要额外的布尔数组或哈希集合。由于每个值最多出现两次,每个负号只表示对应值已经被处理过,不会把同一个重复值加入多次。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector findDuplicates(std::vector& nums) { std::vector result; for (int value : nums) { int index = std::abs(value) - 1; if (nums[index] < 0) { result.push_back(index + 1); } else { nums[index] = -nums[index]; } } return result; } }; 代码分析 -------- 值与下标的一一映射把“是否出现过”编码进原数组:第一次访问对应位置时变负,第二次访问时检测到负号。遍历过程中始终对当前值取绝对值,因此前面被标记的元素仍能作为后续输入使用。每个元素只处理一次,时间复杂度为 ``O(n)``,除返回结果外额外空间复杂度为 ``O(1)``。