Найти дубликат

Описание (LeetCode - 287. Find the Duplicate Number)

Дан массив nums, содержащий n + 1 целых чисел. Каждое число находится в диапазоне от 1 до n включительно.

В массиве есть ровно одно повторяющееся число. Нужно вернуть это число.

Массив нельзя изменять. Решение должно использовать только O(1) дополнительной памяти.

Пример 1:

nums = [1, 3, 4, 2, 2]

Результат:

2

Пример 2:

nums = [3, 1, 3, 4, 2]

Результат:

3

Пример 3:

nums = [3, 3, 3, 3, 3]

Результат:

3

Ограничения:

• 1 <= n <= 10⁵
• nums.length == n + 1
• 1 <= nums[i] <= n
• В массиве есть ровно одно повторяющееся число, но оно может встречаться больше двух раз