8. Longest Consecutive Sequence

«Любая цепочка начинается с первого звена. Если отсечь звенья из середины и исследовать только начала, квадратичный поиск превращается в линейный взмах».
— Брайан Керниган

💡 Связанные темы:

• 1. Теория. Хеш таблицы — множество на пустых структурах struct{}
• 7. Contains Duplicate — дедупликация элементов
• 9. Insert Delete GetRandom O1 — гибридизация структур данных
• 15. Union Find: 1. Теория — динамическое объединение смежных компонент

Введение: Кажущийся тупик квадратичной сложности

Задача Longest Consecutive Sequence (LeetCode 128) — образец алгоритмической элегантности:

Дан неотсортированный массив целых чисел nums. Найти длину самой длинной последовательности элементов, идущих подряд в числовом ряду (например, [1, 2, 3, 4]).
Жесткое требование: алгоритм обязан работать за строго линейное время $O(N)$.

Первый инстинкт программиста — отсортировать массив за $O(N \log N)$ и линейно подсчитать максимальный непрерывный отрезок.
Но условие задачи бескомпромиссно: только $O(N)$. Сортировка запрещена правилами игры.

Как же обнаружить соседние числа в хаотичном массиве за один проход?

🎯 Вопросы для уточнения условий (Interview Warm-up)

1. Дубликаты в массиве:
   «Может ли массив содержать дублирующиеся числа (например, [1, 2, 0, 1])?»
   (Да, дубликаты должны учитываться в последовательности ровно один раз: длина [0, 1, 2] равна 3).
2. Отрицательные числа:
   «Могут ли числа быть отрицательными?»
   (Да, поддерживаются любые целые числа: [-2, -1, 0, 1]).
3. Размер массива и пустой ввод:
   «Что возвращать для пустого массива []?»
   (Возвращаем 0).

Золотой инвариант: Поиск начал последовательностей

Представьте, что мы занесли все числа в хеш-множество numSet := make(map[int]struct{}) за $O(N)$.
Теперь мы можем за $O(1)$ проверить наличие любого числа.

Если для каждого числа $x$ мы начнем проверять $x+1, x+2, \dots$, мы рискуем скатиться к $O(N^2)$ (для массива [1, 2, 3, 4, 5] мы бы стартовали обход и от 1, и от 2, и от 3...).

Ключевой инсайт:
Число $x$ является началом последовательности тогда и только тогда, когда в множестве отсутствует его предшественник:
$$x - 1 \notin \text{numSet}$$

Если $x - 1$ уже есть в множестве, значит, текущее число $x$ — это середина или конец цепочки, которую мы обязательно раскрутим (или уже раскрутили) от ее истинного начала. Мы просто пропускаем его!

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:2px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc

    A["Массив: [100, 4, 200, 1, 3, 2]"]:::entry --> B["Строим множество numSet за O(N)"]:::process
    B --> C["Проверяем число x = 4:<br/>есть ли (4 - 1 = 3) в множестве?"]:::process
    C -- "Да (3 есть!)" --> D["Пропускаем 4 — это не начало!"]:::warning
    B --> E["Проверяем число x = 1:<br/>есть ли (1 - 1 = 0) в множестве?"]:::accent
    E -- "Нет (0 отсутствует!)" --> F["1 — это ИСТИННОЕ НАЧАЛО!"]:::success
    F --> G["Раскручиваем цепочку: 1 -> 2 -> 3 -> 4<br/>Длина streak = 4"]:::success
  

🛠️ Оптимальное решение на Go

package consecutive

// LongestConsecutive находит длину самой длинной непрерывной последовательности за O(N).
func LongestConsecutive(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    // Шаг 1: переносим все элементы в хеш-множество за O(N)
    set := make(map[int]struct{}, len(nums))
    for _, num := range nums {
        set[num] = struct{}{}
    }

    longest := 0

    // Шаг 2: ищем только начала последовательностей
    for num := range set {
        // Если num-1 отсутствует, значит num — начало цепочки!
        if _, hasPrev := set[num-1]; !hasPrev {
            current := num
            streak := 1

            // Раскручиваем цепочку вправо
            for {
                if _, hasNext := set[current+1]; hasNext {
                    current++
                    streak++
                } else {
                    break
                }
            }

            if streak > longest {
                longest = streak
            }
        }
    }

    return longest
}

📊 Доказательство сложности $O(N)$

Почему вложенный цикл for не делает алгоритм квадратичным?

1. Внешний цикл проходит по каждому уникальному числу ровно 1 раз.
2. Внутренний цикл for запускается исключительно для начал цепочек.
3. Каждое число $x$ массива входит ровно в одну непрерывную последовательность. Поэтому внутренний цикл посетит каждое число массива строго один раз за все время работы программы!
4. Итоговое количество операций: $N$ (построение множества) $+ N$ (внешний цикл) $+ N$ (внутренний цикл) $= 3N \in O(N)$.

⚙️ Mechanical Sympathy: Память и кэш-линии

🏭 Применение в System Design: Детекция непрерывных последовательностей

1. Анализ логов безопасности (SIEM / Audit Trails):
   Поиск непрерывных диапазонов скомпрометированных портов или последовательных IP-адресов подсети бота.
2. Восстановление пропущенных сообщений (Message Sequence Numbers):
   В протоколах гарантированной доставки (TCP SACK, финансовые FIX-протоколы) при получении пачки пакетов не по порядку требуется определить непрерывный диапазон доставленных номеров транзакций и выявить «дыры» для повторного запроса.
3. Union-Find для стриминга:
   В потоковых системах, где числа приходят в реальном времени, вместо периодической перестройки множества применяют структуру Disjoint Set Union (Union-Find): приход числа $x$ объединяет множества $[x-1]$ и $[x+1]$ за почти константное время $O(\alpha(N))$.

🗺️ Навигация