# 442. Find All Duplicates in an Array

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]

思路& 代码

注意题目里面的assumption： 1 ≤ a[i] ≤n，所以可以用index代表这个数

从头到尾走一遍，如果没有遇到过这个数i，就把i-1变成负数-(i-1)，如果已经遇到过这个数（该index - 1上的数为负数），那么久把这个数添加到答案里。

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if(len <= 1) {
            return res;
        }
        for(int i = 0; i < len; i++) {
            int index = Math.abs(nums[i]) - 1;
            if(nums[index] > 0) {
                nums[index] = -nums[index];
            } else {
                res.add(-nums[index]);
            }
        }
        return res;
    }

所以时间复杂度就是O(n)