# LeetCode Solution, Easy, 448. Find All Numbers Disappeared in an Array

# [448. Find All Numbers Disappeared in an Array](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)

## 題目敘述

Given an array `nums` of n integers where `nums[i]` is in the range `[1, n]`, return _an array of all the integers in the range `[1, n]` that do not appear in `nums`_.

**Example 1:**

    Input: nums = [4,3,2,7,8,2,3,1]
    Output: [5,6]

**Example 2:**

    Input: nums = [1,1]
    Output: [2]

**Constraints:**

- `n == nums.length`
- `1 <= n <= 10**5`
- `1 <= nums[i] <= n`

**Follow up:** Could you do it without extra space and in `O(n)` runtime? You may assume the returned list does not count as extra space.

### 題目翻譯

在一個整數的陣列中，找出在 `[1, n]` 的範圍內不包含的值有哪些。例如陣列長是 3，那就是 1~3 的值，有哪些不在陣列中。如果陣列是 `[1, 1, 3]`，那就會是 `2`。

## 解法解析

解法的重點不外乎就是要記住，哪些值已經檢查過。第一種解法就是使用 Hash Table 的方式來記錄哪些值已經檢查過了，但因為使用 Hash Table 空間複雜度的就比較高 `O(n)`。想要維持住 `O(n)` 的時間複雜度又要降低空間度雜度的話，就是會想到 In-place 了，所以第二個解法就是使用 In-place。

這邊 In-place 的解法是滿巧妙的運用，將值當作 Index 的方式。因為排序過後的話，該位置的值應該會相當於 `index + 1 = value`。將該值變成負值，最後查詢哪些 value 依舊是正數，那就知道了哪些值不存在。

```
[1, 1, 3] 
遍歷 index = 0, value = 1 ==> [-1, 1, 3]
遍歷 index = 1, value = 1 ==> [-1, 1, 3], index 0 已經是負值，所以不變動
遍歷 index = 2, value = 3 ==> [-1, 1, -3]
剩下 index 2 是正數，所以不存在的值是 2
```

### 解法範例

#### Go

##### Using Hash Map

```go
func findDisappearedNumbers(nums []int) []int {
	var hashTable = make(map[int]bool)

	for _, num := range nums {
		hashTable[num] = true
	}

	var result []int
	for i := 1; i <= len(nums); i++ {
		if _, ok := hashTable[i]; !ok {
			result = append(result, i)
		}
	}
	return result
}
```

##### O(1) Space InPlace Modification Solution

```go
func findDisappearedNumbers(nums []int) []int {
	for _, num := range nums {
		var newIndex int = num
		if num < 0 {
			newIndex = -num
		}
		newIndex--

		if nums[newIndex] > 0 {
			nums[newIndex] *= -1
		}
	}

	var result []int
	for i, num := range nums {
		if num > 0 {
			result = append(result, i+1)
		}
	}
	return result
}
```

#### JavaScript

##### Using Hash Map

```javascript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function (nums) {
    const hashTable = {};

    for (const num of nums) {
        hashTable[num] = true;
    }

    const result = [];

    for (let i = 1; i <= nums.length; i++) {
        if (!hashTable[i]) {
            result.push(i);
        }
    }
    return result;
};
```

##### O(1) Space InPlace Modification Solution

```javascript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function (nums) {
    for (const num of nums) {
        let newIndex = Math.abs(num) - 1;

        if (nums[newIndex] > 0) {
            nums[newIndex] *= -1;
        }
    }

    const result = [];

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.push(i + 1);
        }
    }
    return result;
};
```

#### Kotlin

##### Using Hash Map

```kotlin
class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        var hashTable = HashMap<Int, Int>()
        for (num in nums) {
            hashTable[num] = 1
        }

        var result = ArrayList<Int>()
        for (i in 1..nums.size) {
            if (!hashTable.containsKey(i)) {
                result.add(i)
            }
        }
        return result
    }
}
```

##### O(1) Space InPlace Modification Solution

```kotlin
class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        for (i in nums.indices) {
            val index = Math.abs(nums[i]) - 1
            if (nums[index] > 0) {
                nums[index] = -nums[index]
            }
        }

        val result = mutableListOf<Int>()
        for (i in nums.indices) {
            if (nums[i] > 0) {
                result.add(i + 1)
            }
        }

        return result
    }
}
```

#### PHP

##### Using Hash Map

```php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function findDisappearedNumbers($nums)
    {
        $hashTable = [];
        foreach ($nums as $num) {
            $hashTable[$num] = 1;
        }

        $result = [];
        for ($i = 1; $i <= count($nums); $i++) {
            if (!isset($hashTable[$i])) {
                $result[] = $i;
            }
        }
        return $result;
    }
}
```

##### O(1) Space InPlace Modification Solution

```php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function findDisappearedNumbers($nums)
    {
        foreach ($nums as $num) {
            $index = abs($num) - 1;
            $nums[$index] = -abs($nums[$index]);
        }

        $result = [];
        foreach ($nums as $i => $num) {
            if ($num > 0) {
                $result[] = $i + 1;
            }
        }
        return $result;
    }
}
```

#### Python

##### Using Hash Map

```python
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        # Hash table for keeping track of the numbers in the array
        # Note that we can also use a set here since we are not
        # really concerned with the frequency of numbers.
        hash_table = {}

        # Add each of the numbers to the hash table
        for num in nums:
            hash_table[num] = 1

        # Response array that would contain the missing numbers
        result = []

        # Iterate over the numbers from 1 to N and add all those
        # that don't appear in the hash table.
        for num in range(1, len(nums) + 1):
            if num not in hash_table:
                result.append(num)

        return result
```

##### O(1) Space InPlace Modification Solution

```python
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        # Iterate over each of the elements in the original array
        for num in nums:

            # Treat the value as the new index
            new_index = abs(num) - 1

            # Check the magnitude of value at this new index
            # If the magnitude is positive, make it negative
            # thus indicating that the number nums[i] has
            # appeared or has been visited.
            if nums[new_index] > 0:
                nums[new_index] *= -1

        # Response array that would contain the missing numbers
        result = []

        # Iterate over the numbers from 1 to N and add all those
        # that have positive magnitude in the array
        for i, num in enumerate(nums):
            if num > 0:
                result.append(i + 1)

        return result
```

#### Rust

```rust
```

#### Swift

##### Using Hash Map

```swift
class Solution {
    func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
        var hashTable: [Int: Bool] = [Int: Bool]()
        for num: Int in nums {
            hashTable[num] = true
        }

        var result: [Int] = [Int]()
        for i: Int in 1...nums.count {
            if hashTable[i] == nil {
                result.append(i)
            }
        }
        return result
    }
}
```

##### O(1) Space InPlace Modification Solution

```swift
class Solution {
    func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
        var nums: [Int] = nums
        for i: Int in nums {
            nums[i - 1] = -abs(nums[i - 1])
        }

        var result: [Int] = [Int]()
        for (i, num) in nums.enumerated() {
            guard num < 0 else {
                result.append(i + 1)
                continue
            }
        }

        return result
    }
}
```