# One brush 312 - simple repetition set - Sword finger offer 03 Duplicate number in array (E)

2022-04-23 15:40:00

`````` subject ：
Find the repeated numbers in the array .

At a length of  n  Array of  nums  All the numbers in  0～n-1  Within the scope of . Some numbers in the array are repeated ,
But I don't know how many numbers are repeated , I don't know how many times each number has been repeated . Please find any duplicate number in the array .
---------------------------
Example  1：
Input ：
[2, 3, 1, 0, 2, 5, 3]
Output ：2  or  3

Limit ：
2 <= n <= 100000
-------------------
Ideas ：  Traversal array
Because you only need to find any duplicate number in the array , So iterate through the array , If you encounter a duplicate number, return .
To determine whether a number is repeated , Use collections to store numbers that have been encountered , If you encounter a number that is already in the set ,
The current number is a duplicate number .

The initialization set is empty , Repeated numbers  repeat = -1
Traversal of each element in an array ：
Add this element to the collection , Judge whether the addition is successful
If the addition fails , Indicates that the element is already in the collection , So this element is a repeating element , Assign the value of this element to  repeat, And end the traversal
return  repeat
------------------
Complexity analysis
Time complexity ：O(n)
Traverse the array once . Use hash set （HashSet）, The time complexity of adding elements is  O(1), Therefore, the total time complexity is  O(n)
Spatial complexity ：O(n). Every element that is not repeated may be stored in the collection , So occupy  O(n)  Extra space .
--------------------
class Solution {

public int findRepeatNumber(int[] nums) {

Set<Integer> set = new HashSet<>();
for (int num : nums) {

if (set.contains(num)) return num;