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

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