Условие

Дан массив nums с целочисленными значениями. Необходимо найти длину самой длинной последовательности элементов в массиве. Напишите функцию longest_consecutive_sequence(nums: List[int]) -> int, которая принимает на вход неотсортированный массив целых чисел nums и возвращает целое число - длину самой длинной последовательности элементов в массиве.

Примеры

Пример 1:

Ввод: nums = [100, 4, 200, 1, 3, 2]
Вывод: 4
Пояснение: Самая длинная последовательность - [1, 2, 3, 4]. Её длина - 4.

Пример 2:

Ввод: nums = [0,3,7,2,5,8,4,6,0,1]
Вывод: 9
Пояснение: Самая длинная последовательность - [0,1,2,3,4,5,6,7,8]. Её длина - 9.

Решение

Для решения задачи будет использоваться алгоритм нахождения длины последовательности элементов в массиве.

1. Создадим множество num_set из массива чисел nums.
2. Инициализируем longest_seq_len в 0.
3. Для каждого элемента num в num_set:
   1. Если num - 1 не находится в num_set, то это начало последовательности. Инициализируем curr_seq_len в 1.
   2. Иначе, продолжаем текущую последовательность. Увеличиваем curr_seq_len на 1.
   3. Если curr_seq_len больше longest_seq_len, то обновляем longest_seq_len значением curr_seq_len.
4. Возвращаем longest_seq_len.

Объяснение с примером

Пусть дан массив nums = [100, 4, 200, 1, 3, 2].

1. Создадим множество num_set = {1, 2, 3, 4, 100, 200}.
2. Инициализируем longest_seq_len в 0.
3. Для каждого элемента num в num_set:
   1. num = 1. num - 1 = 0 не находится в num_set. curr_seq_len инициализируется в 1.
   2. num = 2. num - 1 = 1 находится в num_set. curr_seq_len увеличивается на 1, становится равным 2.
   3. num = 3. num - 1 = 2 находится в num_set. curr_seq_len увеличивается на 1, становится равным 3.
   4. num = 4. num - 1 = 3 находится в num_set. curr_seq_len увеличивается на 1, становится равным 4.
   5. num = 100. num - 1 = 99 не находится в num_set. curr_seq_len инициализируется в 1.
   6. num = 200. num - 1 = 199 не находится в num_set. curr_seq_len инициализируется в 1.
4. Возвращаем longest_seq_len, равный 4.

Код на Python