Given an array of integers `nums` containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Return the duplicate number.
nums = array of n+1 integers where each integer is in range [1, n]
the duplicate integer
Example 1:
Input:
nums = [1,3,4,2,2]
Output:
2
Explanation:
2 is the duplicate.
Example 2:
Input:
nums = [3,1,3,4,2]
Output:
3
Explanation:
3 is the duplicate.
Example 3:
Input:
nums = [1,1]
Output:
1
Explanation:
1 is the duplicate (appears twice).