数组中消失的数字

题目：找到所有数组中消失的数字
描述：给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
来源：力扣（LeetCode）448. 找到所有数组中消失的数字
举例：

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

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

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
题解：
【方式一】使用一个临时数组进行统计
例如：创建一个临时的数组，数组的长度与原数组长度一致，当原数组每出现一次，就在临时数组的【索引-1】处将值+1记为出现的次数，遍历原数组结束后，临时数组中仍为0的元素，其【索引+1】即为目标值
原数组：[4,3,2,7,8,2,3,1]
临时数组：[0,0,0,0,0,0,0,0]
第1次遍历：[0,0,0,1,0,0,0,0]
第2次遍历：[0,0,1,1,0,0,0,0]
第3次遍历：[0,1,1,1,0,0,0,0]
第4次遍历：[0,1,1,1,0,0,1,0]
第5次遍历：[0,1,1,1,0,0,1,1]
第6次遍历：[0,2,1,1,0,0,1,1]
第7次遍历：[0,2,2,1,0,0,1,1]
第8次遍历：[1,2,2,1,0,0,1,1]

public List<Integer> findDisappearedNumbers(int[] nums) {
    int[] tempArrays = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        //遍历数组，每出现一个元素就将这个元素值添加到临时数组的索引-1的位置
        tempArrays[nums[i]-1]++;
    }
    List<Integer> resultList = new ArrayList<>(nums.length/2);
    for (int i = 0; i < tempArrays.length; i++) {
        //遍历临时数组，如果当前位置的值<1,说明没有出现过
        if(tempArrays[i] < 1){
            resultList.add(i+1);
        }
    }
    return resultList;
}

【方法二】使用set集合辅助
例如：创建一个set集合，遍历原数组，将原数组中元素添加到set集合中，最终声明一个次数为原数组大小的循环，依次判断当前值是否存在于set集合中，如果不存在即为目标值。

public List<Integer> findDisappearedNumbers1(int[] nums){
    Set<Integer> numsSet = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        //将数组中的每一位元素添加到set集合
        numsSet.add(nums[i]);
    }
    List<Integer>  resultList = new ArrayList();
    for (int i = 1; i < nums.length+1; i++) {
        //循环从1开始，如果当前的i不在set集合中，就是目标值
        if(!numsSet.contains(i)){
            resultList.add(i);
        }
    }
    return resultList;
}

【方法三】将数组本身的值置为相反数，这种方式不会使用额外的空间
例如：我们仔细观察这个原数组，发现可以使用他的索引对应位置的关系
原数组：4,3,2,7,8,2,3,1
索引值：0,1,2,3,4,5,6,7
期望值：1,2,3,4,5,6,7,8
我们遍历这个原数组，让原数组中的值的期望值，对应的索引位置的值，置为负数

此时遍历完成后，原数组中仍然为正数的值对应的【索引+1】的值即为目标值
注意：由于每次我们都改变了原数组，所以在每次取原数组中的值的时候，需要取绝对值，否则会出现索引越界

public List<Integer> findDisappearedNumbers2(int[] nums){
    List<Integer> resultList = new ArrayList<>(nums.length/2);
    for (int i = 0; i < nums.length; i++) {
        //由于每次我们都改变了原数组，所以在每次取原数组中的值的时候，
        //需要取绝对值，否则会出现索引越界异常
        int num = Math.abs(nums[i]);
        int index = num - 1;
        if(nums[index] > 0){
            nums[index] = -nums[index];
            System.out.println(Arrays.toString(nums));
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] > 0){
            resultList.add(i+1);
        }
    }
    return resultList;
}