题目要求
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~n之间，其中n是数组的长度。有的元素出现了一次，而有的元素出现了两次。找到数组中所有出现两次的数字。
思路一：交换
为了在O(N)的时间内找到所有的出现两次的数字，其核心要求在于用现有的数组记录已经访问过的元素，同时不会丢失尚未访问过的元素。思路一采用交换的核心思想，即每次都将当前下标上的值和以该值为下标的位置上的值进行交换，如果该值下标位置上的值和其相等，则说明该数字已经被遍历过一遍了。
代码如下：
public List<Integer> findDuplicates(int[] nums) { int index = 0; List<Integer> result = new ArrayList<Integer>(); while(index < nums.length) { int num = nums[index]; if(num == 0){ index++; }else if (nums[num-1] == num) { if(index != num-1){ result.add(num); nums[index] = 0; } index++; }else{ swap(index, num-1, nums); } } return result; } public void swap(int i, int j, int[] nums) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }思路二：取反
有没有一种办法在既保留当前位置上的值nums[i]的同时，又能够用某种方式记录i+1是否已经被访问过了？可以通过取反的方法来记录是否被访问过这个情况。如果访问到下标为i的位置上的值，则去判断nums[nums[i]-1]位置上的值是否为负数，如果是，则说明num[i]出现了两次，否则将nums[nums[i]-1]位置上的值取反保留。
代码如下：
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; }