Question

题目内容

解题思路

哈希的数组替代法。

nums 数组中一定存在重复的数字，nums 中的数字一定属于 [1, n]。

在第一个 for 循环中更改了 nums 的部分值，对于 nums[i] 的值改变次数是由出现了多少次 i + 1 值。数 i 若存在则下标是 i - 1 这个位置的数一定大于 n，被改变了。

[4, 3, 2, 7, 8, 2, 3, 1] ​ 在第一个 for 循环结束后是 [12, 19, 18, 15, 8, 2, 11, 9] n = 8 ​。

nums[1] = 3 被改变了 2 次得到 19 即出现了两次 2，nums[2] = 2 被改变了 2 次变成了 18 即出现了两次 3。

代码实现

const findDisappearedNumbers = (nums: number[]): number[] => {
  const n: number = nums.length;
  for (const num of nums) {
    const x: number = (num - 1) % n;
    nums[x] += n;
  }
  const ret: number[] = [];
  for (const [i, num] of nums.entries()) {
    if (num <= n) {
      // 下标是 i，题目中要求的值为 i + 1
      ret.push(i + 1);
    }
  }
  return ret;
};