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

一 题目：

二 思路：

• 不考虑空间正常思路我们可以创建一个长度为n的数组，把每个值填进去，然后最后为空的那个位置就是缺少的
• 但是由于不能创建额外空间，那么这里我们注意到，这个数组长度为n，那么其实我们可以用nums染色（置负）来表示数字是否存在
• 最后进行遍历看看哪个位置没有被染色（置负）即可

三 代码：

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //染色法，将每个索引i代表i+1的值是否有
        for (int i = 0; i < nums.length; i++) {
            int curr=Math.abs(nums[i]);
            int index=curr-1;
            if (nums[index]>0){
                nums[index]=-nums[index];
            }
        }

        List<Integer> res=new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>0){
                res.add(i+1);
            }
        }
        return res;
    }
}