困难

问题描述

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示：

• nums.length <= 30000

标记

设数组长度为 $n$，那么数据范围最大是 $[1, n + 2]$，因此，可以将 $nums[Math.abs(nums[i]) - 1]$ （由于是下标，所以需要减一）设置为负数，用于标记 $|nums[i]|$ 这个数存在，由于 $|nums[i]| - 1 \geq n$，因此可以创建一个长度不大于 $2$ 的数组 $overflow$ 记录次部分数据。然后从下标[0, n+1] 遍历，若某个下标为 $i$ 的数数为正数，或 $overflow$ 中不存在记录 $i$, 则说明数字 $i + 1$ 不存在，当结果集满两个即可返回。

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

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$