难度：中等 题目描述 解题思路 不使用额外空间，而且时间复杂度O(n)，那就原地哈希了 思路很清楚，就是把每个数字放到对应的下标处，如果最后不对应，就是重复出现的数字
/* * 442. 数组中重复的数据 * 2020/7/2 */ public static List<Integer> findDuplicates(int[] nums) { List<Integer> re = new LinkedList<>(); for (int i = 0; i < nums.length; i++) { while(nums[i] != i+1) { if(nums[nums[i]-1] == nums[i]) { //防止出现死循环 break; } int temp = nums[nums[i]-1]; nums[nums[i]-1] = nums[i]; nums[i] = temp; } } for (int i = 0; i < nums.length; i++) { if(nums[i] != i-1) re.add(nums[i]); } return re; }看到一种很巧妙的办法，把数组元素当成索引，每次把索引位置的数字变成负数，这样遍历的时候遇到负数，就知道这个位置之前出现过 比如 4 3 2 7 8 2 3 1 第一次把4对应的下标3变成-7 4 3 2 -7 8 2 3 1 然后是3—>4 3 -2 -7 8 2 3 1 然后是2—>4 -3 -2 -7 8 2 3 1 然后是7—>4 -3 -2 -7 8 2 -3 1 然后是8—>4 -3 -2 -7 8 2 -3 -1 然后是2，发现-1已经是负数，说明2这个数字以前出现过，添加 然后是3，也出现过，添加 最后是1—>-4 -3 -2 -7 8 2 -3 -1
public List<Integer> findDuplicates(int[] nums) { List<Integer> re = new LinkedList<>(); for (int i = 0; i < nums.length; i++) { int index = Math.abs(nums[i]); if (nums[index - 1] > 0) { //大于0说明没出现过，出现过就变成负数标记 nums[index - 1] *= -1; } else { //如果负数说明出现过 re.add(index); } } return re; }