442. 数组中重复的数据

难度：中等
题目描述

解题思路
不使用额外空间，而且时间复杂度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;}

2、索引标记

看到一种很巧妙的办法，把数组元素当成索引，每次把索引位置的数字变成负数，这样遍历的时候遇到负数，就知道这个位置之前出现过
比如 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;}