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]

1 public class Solution { 2     //使用index和负数来表示这个位置被访问过。 3  4     public List
     
       findDuplicates(int[] nums) { 5         List
      
        res = new ArrayList<>(); 6         for (int i = 0; i < nums.length; ++i) { 7             int index = Math.abs(nums[i]) - 1; 8             if (nums[index] < 0) { 9                 res.add(Math.abs(index + 1));10             }11             nums[index] = -nums[index];12         }13         return res;14     }15 }