Код Senior Массивы и хеш-таблицы обновлено
Самая длинная цепочка подряд
Условие
Длина самой длинной последовательности идущих подряд чисел (порядок в массиве не важен). Сортировать нельзя - нужна линейная сложность.
Примеры
longestConsecutive([100, 4, 200, 1, 3, 2]) // 4
longestConsecutive([]) // 0
longestConsecutive([1, 1, 1]) // 1
Как подойти
Наивно тут напрашивается сортировка за O(n log n). Приём: перебираем только начала цепочек, поэтому внутренний while суммарно отработает не больше n раз - получается O(n). Проверка set.has(n-1) - вся соль.
Подсказки: 2
- Считай длину только от начала цепочки.
- Число является началом, если предыдущего в множестве нет.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.