[LeetCode] 442. Find All Duplicates in an Array

【原题】 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]

【解释】 给定一个含有那个元素的数组， 数组中的元素要么出现一次要么出现两次，要求找出数组中所有的重复元素。 【思路】 因为数组元素的取值都不会越界，且数组只有出现一次和两次良好总可能性，那么可以把书组元素当成是数组的index。循环每次index-1的数乘上-1，若该index-1元素已经为负数，则说明该index之前已经出现过，故必为重复元素，将其加到list即可。

因为这里最多出现两次，所以不需要判断要加入的元素是否会存在list中，刚开始博主就是这样的思想，判断会增加时间复杂度，最终最后一个测试用例不通过，会后换成hashset，再转成list才通过[捂脸]。

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list=new ArrayList<Integer>();
        //HashSet<Integer> hashSet=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            int index=Math.abs(nums[i]);
            if(nums[index-1]<0) //若该index已经为负数，说明前面已经出现过，则这个index肯定是重复的元素
                 list.add(index);
            nums[index-1]*=-1;
        }
        return list;

    }
}