Самая длинная последовательная последовательность
Дан массив целых чисел 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
Оптимизируйте поиск, начиная только с чисел, которые могут быть началом последовательности (т.е. когда число на единицу меньше не существует в множестве).