442. 数组中重复的数据

442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例 1：
输入：nums = [4,3,2,7,8,2,3,1] 输出：[2,3]
示例 2：
输入：nums = [1,1,2] 输出：[1]
示例 3：
输入：nums = [1] 输出：[]

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n
• nums 中的每个元素出现 一次 或 两次

思路

将输入空间作为是否出现过的标记，因为长度为 n，所以一定不会越界。遍历一次数组，每次都对元素取绝对值，然后判断下标 Math.abs(nums[i])-1 的元素是否为正数，是的话说明这个元素第一次出现，将这个下标的元素设为负数；不是的话说明已经出现过一次了，加入结果数组中，最后返回即可。

解答

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