> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/find-all-numbers-disappeared-in-an-array.md).

# Find All Numbers Disappeared in an Array

<https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/>

> Given an array of integers where 1 ≤ a\[i] ≤n(n= size of array), some elements appear twice and others appear once.
>
> Find all the elements of \[1,n] inclusive that do not appear in this array.
>
> Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
>
> Input:
>
> \[4,3,2,7,8,2,3,1]
>
> Output:
>
> \[5,6]

## Thoughts

不让用额外的space并且要O(N)时间, 必须要利用i和nums\[i]的关系. 如果一个不缺, nums\[i]里存的应该是i+1. 所以可以把nums\[nums\[i] - 1]做特殊标记, 这样当重新遍历到i时看到标记就能知道i + 1出现过. 那么如何做标记呢? 刚开始想把nums\[nums\[i] - 1]存为0, 但这么做有个问题, 比如\[2,1], 会变成\[2, 0], 那就不知道1出现过了. 有种比较巧妙的方法既能保留标记又能保留原index, 即取负数. 比如\[2,1, 2]变成\[-2, -1, 2], 那我们就能知道1和2对应的i = 0和1时出现过, 但3对应的2没出现过.

## Code

```
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int pos = Math.abs(nums[i]) - 1;
            if (nums[pos] >= 0) {
                nums[pos] = -nums[pos];
            }
        }

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

        return res;
    }
}
```

## Analysis

时间复杂度O(N), 空间O(1).