Самая длинная последовательная последовательность

Дан массив целых чисел nums. Верните длину самой длинной последовательной последовательности элементов, которую можно сформировать.

Последовательная последовательность - это последовательность элементов, в которой каждый элемент ровно на 1 больше предыдущего. Элементы не обязательно должны быть последовательными в исходном массиве.

Вы должны написать алгоритм, который работает за время O(n).

Пример 1:

Input: nums = [2,20,4,10,3,4,5]

Output: 4
Объяснение: Самая длинная последовательная последовательность - [2,3,4,5].

Пример 2:

Input: nums = [0,3,2,5,4,6,1,1]

Output: 7

Рекомендуемая временная и пространственная сложность

Вам следует стремиться к решению с временной сложностью O(n) и пространственной сложностью O(n), где n — размер входного массива.


Подсказка 1

Сортировка массива даст вам O(n log n) решение. Как можно достичь O(n)?


Подсказка 2

Используйте хеш-множество для мгновенного поиска чисел. Для каждого числа проверяйте, существует ли число на единицу больше.


Подсказка 3

Оптимизируйте поиск, начиная только с чисел, которые могут быть началом последовательности (т.е. когда число на единицу меньше не существует в множестве).

Эта задача проверяет способность эффективно находить последовательные числа в неотсортированном массиве. Она помогает развивать навыки работы с хеш-множествами и оптимизации алгоритмов. Решение требует понимания временной сложности и умения работать с последовательностями чисел.

Входные параметры :

[2,20,4,10,3,4,5]

Ожидаемый результат

4