# LeetCode Challenge — Find All Duplicates in an Array 8/6 #442

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]

Oh~The importance of this problem is ….

Could you do it without extra space and in O(

n) runtime?

When I view this problem, I got two ideas off the top of my head. Dictionary? Map? Finally, I do it via Map. Because when I used Dictionary, I got Compile Error at Leetcode. I knew have a solution is used Math.abs.

First, we need to view this table from 初学者应该了解的数据结构：Array、HashMap 与 List.

We knew that the time complexity of **HashMap get()** is O(1). But! Why? I reference this articles.

Time Complexity of HashMap get is O(1). Why?

and

How HashMap works in Java

- Get index, calculate the index based on the key.
- Get the index position according to the index
- Obtain the key-value pair LinkList corresponding to the index position
- Traverse the key-value pair LinkList and find the corresponding Entry key-value pair according to the key.
- Get the value.