Description,
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

The leetcode link

Using array index to store the “extra piece of information”.

When a number i, flip the position i-1 in the array to negative.
When the duplicated number i is encountered, you will see the number stored at position i-1 is a negative one.
Then you found one.

repeat this to the end of the array.

Time complexity: O(n)

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums:   List[int]
        :rtype:       List[int]
        :runtime:     632ms
        :faster than: 50%
        """
        ret = []
        for num in nums:
            if nums[abs(num)-1] < 0:
                ret.append(abs(num))
            else:
                nums[abs(num)-1] *= -1
        return ret

imgRuntime:632ms