Find All Duplicates in an Array

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]

Hint

Train of Thought

对每个数字,比如4, 找到它对应的index3, 看那个index上的数字, 如果第一次出现这个数字, 就把它对应index(3)上的数字变成负的, 如果又出现了一次4,再找到index 3上对应的数字, 发现这个数字是负的, 就把它加到res

Code

public class Solution {
    // when find a number i, flip the number at position i-1 to negative. 
    // if the number at position i-1 is already negative, i is the number that occurs twice.

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0)
                res.add(Math.abs(index+1));
            nums[index] = -nums[index];
        }
        return res;
    }
}

Complexity