# 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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/find-all-numbers-disappeared-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.