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

示例 1

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

示例 2

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

解题

方法 1

先把1 - n的数字放在一个list中，然后遍历给定的数组，在list中直接删除数组中存在的元素，直接返回list即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        LinkedList<Integer> res = new LinkedList<>();
        int len = nums.length;
        for (int i = 1; i <= len; i++) {
            res.add(i);
        }
        for (int i = 0; i < len; i++) {
            res.removeFirstOccurrence(nums[i]);
        }
        return res;
    }
}

方法 2

利用set 和 list，先把数组数据放到set集合里，从1-n遍历set里不包含的元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int len = nums.length;
        Set<Integer> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();

        for (int num : nums) {
            set.add(num);
        }

        for (int i = 1; i <= len; i++) {
            if (!set.contains(i)) {
                list.add(i);
            }
        }
        return list;
    }
}

方法 3

先对数组排序，用一个变量记录期望的数字，比较当前数字与期望数字，找出缺失的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> findMissingNumbers(int[] nums) {
    List<Integer> result = new ArrayList<>();
    int n = nums.length;

    int expectedSum = (n * (n + 1)) / 2;

    int actualSum = 0;
    for (int num : nums) {
        actualSum += num;
    }
    int missingNumber = expectedSum - actualSum;
    result.add(missingNumber);
    return result;
}