448.找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

1
2
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

1
2
输入：nums = [1,1]
输出：[2]

和268.丢失的数字对应，不过在268中，只会有一个数字丢失，而在此题中丢失的数字可能有很多个

Solution：

一般的思路是用哈希表记录数组nums中的数字，然后查询缺失的数字，由于数字范围在1~n内，我们也可以用长度为n的数组来代替哈希表

nums的长度恰好为n，为什么不让nums自身来代替哈希表呢？

方法的核心思想是利用数组自身作为哈希表来标记出现过的数字，最后遍历数组，未被标记的索引位置即对应消失的数字。下面是对这个方法的详细注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    // findDisappearedNumbers方法接收一个整数数组nums作为参数，返回数组中所有消失的数字
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length; // n为数组的长度
        // 第一次遍历数组，使用数组本身来标记数字是否出现过
        for (int num : nums) {
            // 计算当前元素应该标记的索引位置，由于可能多次遍历到相同的数，使用模n确保索引有效
            int x = (num - 1) % n;
            // 在对应的索引位置加n，如果某个数字出现过，其对应索引位置的值将会大于n
            nums[x] += n;
        }
        // 创建一个列表，用于存放所有消失的数字
        List<Integer> ret = new ArrayList<Integer>();
        // 第二次遍历数组，找出所有值未大于n的索引位置，这些位置加1即为消失的数字
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                // 如果nums[i]的值未大于n，说明i+1这个数字没有出现过
                ret.add(i + 1);
            }
        }
        // 返回消失的数字组成的列表
        return ret;
    }
}