Find All Duplicates in an Array

投稿日 |

Description

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?

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Method

要在O(n)时间复杂度之内完成的话，就只能遍历一次数组。扫一遍数组然后将扫描过的数放进HashSet里，然后判断数有没有在HashSet中即可。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            if(set.contains(nums[i])){
                res.add(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }
        return res;
    }
}