106. Find All Duplicates in an Array

Medium · Array

Given an integer array `nums` of length `n` where all integers are in the range `[1, n]` and each integer appears either once or twice, return an array of all the integers that appear twice.

You must write an algorithm that runs in O(n) time and uses only O(1) extra space (excluding the output array). The order of the output does not matter, but your solution must return the results sorted in ascending order.

Note: Each element in `nums` is guaranteed to be between 1 and n (inclusive), and each element appears at most twice.

Examples

Example 1
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [2, 3]
Explanation: The numbers 2 and 3 each appear twice in the array, so the answer is [2, 3].
Example 2
Input: nums = [1, 1, 2]
Output: [1]
Explanation: The number 1 appears twice, so the answer is [1].

Constraints