Подготовка к алгоритмическим задачам

Самая длинная последовательная последовательность: разбор задачи

10 мин чтения

алгоритмы

массивы

хеш-таблицы

оптимизация

Почему эта задача важна?

Задача на поиск самой длинной последовательной последовательности позволяет оценить:

🧠 Умение работать с неупорядоченными данными
⚡ Навыки оптимизации алгоритмов до линейной сложности
🎯 Способность эффективно использовать хеш-структуры
🔍 Понимание разницы между сортировкой и поиском

Постановка задачи

Формулировка:

Дан массив целых чисел nums. Верните длину самой длинной последовательной последовательности элементов, которую можно сформировать. Последовательная последовательность - это последовательность элементов, в которой каждый элемент ровно на 1 больше предыдущего. Элементы не обязательно должны быть последовательными в исходном массиве. Вы должны написать алгоритм, который работает за время O(n).

Примеры:

// Первый пример ✅
Input: nums = [2, 20, 4, 10, 3, 4, 5]
Output: 4
Объяснение: Самая длинная последовательная последовательность - [2, 3, 4, 5].

// Второй пример ✅
Input: nums = [0, 3, 2, 5, 4, 6, 1, 1]
Output: 7
Объяснение: Самая длинная последовательная последовательность - [0, 1, 2, 3, 4, 5, 6].

// Третий пример ✅
Input: nums = [1, 2, 0, 1]
Output: 3
Объяснение: Самая длинная последовательная последовательность - [0, 1, 2].

Ограничения:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Сортировка и подсчёт (не удовлетворяет требованию O(n)) 📊

function longestConsecutive(nums) {
  if (nums.length === 0) return 0;
  
  // Сортируем массив
  nums.sort((a, b) => a - b);
  
  // Удаляем дубликаты
  const uniqueNums = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] !== nums[i - 1]) {
      uniqueNums.push(nums[i]);
    }
  }
  
  // Ищем самую длинную последовательную последовательность
  let maxLength = 1;
  let currentLength = 1;
  
  for (let i = 1; i < uniqueNums.length; i++) {
    if (uniqueNums[i] === uniqueNums[i - 1] + 1) {
      currentLength++;
      maxLength = Math.max(maxLength, currentLength);
    } else {
      currentLength = 1;
    }
  }
  
  return maxLength;
}

Анализ решения:

✅ Простая реализация и понятная логика

✅ Хорошо работает для небольших массивов

❌ Временная сложность O(n log n) из-за сортировки

❌ Не удовлетворяет требованию задачи о линейном времени O(n)

Решение 2: Использование хеш-множества (оптимальное решение) 🚀

function longestConsecutive(nums) {
  if (nums.length === 0) return 0;
  
  // Создаем хеш-множество для быстрого поиска
  const numSet = new Set(nums);
  
  let maxLength = 0;
  
  // Проходим по каждому элементу массива
  for (const num of numSet) {
    // Проверяем, является ли текущий элемент началом последовательности
    // (если предыдущего элемента нет в множестве)
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentLength = 1;
      
      // Считаем длину последовательности
      while (numSet.has(currentNum + 1)) {
        currentNum++;
        currentLength++;
      }
      
      // Обновляем максимальную длину
      maxLength = Math.max(maxLength, currentLength);
    }
  }
  
  return maxLength;
}

Характеристики:

✅ Оптимальная временная сложность O(n)

✅ Эффективно обрабатывает дубликаты

✅ Не требует сортировки массива

✅ Удовлетворяет всем требованиям задачи

Решение 3: Использование объекта для отслеживания границ последовательностей 🔍

function longestConsecutive(nums) {
  if (nums.length === 0) return 0;
  
  // Объект для отслеживания границ последовательностей
  const sequences = {};
  let maxLength = 0;
  
  for (const num of nums) {
    // Пропускаем, если уже видели этот элемент
    if (sequences[num] !== undefined) continue;
    
    // Ищем левую и правую границы возможной последовательности
    const left = sequences[num - 1] !== undefined ? sequences[num - 1] : 0;
    const right = sequences[num + 1] !== undefined ? sequences[num + 1] : 0;
    
    // Длина текущей последовательности
    const length = left + right + 1;
    
    // Обновляем границы последовательности
    sequences[num] = length;
    sequences[num - left] = length;
    sequences[num + right] = length;
    
    // Обновляем максимальную длину
    maxLength = Math.max(maxLength, length);
  }
  
  return maxLength;
}

Преимущества и недостатки:

✅ Временная сложность O(n)

✅ Требует только одного прохода по массиву

❌ Более сложная логика для понимания

❌ Требует дополнительной памяти для хранения границ

Решение 4: Динамическое программирование с хеш-таблицей 📈

function longestConsecutive(nums) {
  if (nums.length === 0) return 0;
  
  // Создаем хеш-таблицу для отслеживания длин последовательностей
  const lengths = {};
  let maxLength = 0;
  
  for (const num of nums) {
    // Пропускаем, если уже обработали этот элемент
    if (lengths[num] !== undefined) continue;
    
    // Инициализируем длину текущего элемента
    lengths[num] = 1;
    
    // Проверяем, можно ли расширить последовательность влево и вправо
    let left = lengths[num - 1] || 0;
    let right = lengths[num + 1] || 0;
    
    // Общая длина последовательности
    let totalLength = left + right + 1;
    
    // Обновляем длины для границ последовательности
    lengths[num - left] = totalLength;
    lengths[num + right] = totalLength;
    
    // Обновляем максимальную длину
    maxLength = Math.max(maxLength, totalLength);
  }
  
  return maxLength;
}

Особенности:

✅ Линейная временная сложность O(n)

✅ Элегантное решение с использованием ДП

❌ Требует дополнительной памяти O(n)

❌ Немного сложнее для реализации и отладки

Распространённые ошибки

🤦‍♂️ Использование сортировки, что нарушает требование линейного времени
😅 Неправильная обработка дубликатов
🐛 Отсутствие проверки, является ли элемент началом последовательности

Оптимизации

Проверка размера массива перед обработкой

function longestConsecutive(nums) {
  // Быстрая проверка краевых случаев
  if (nums.length === 0) return 0;
  if (nums.length === 1) return 1;
  
  const numSet = new Set(nums);
  let maxLength = 0;
  
  for (const num of numSet) {
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentLength = 1;
      
      while (numSet.has(currentNum + 1)) {
        currentNum++;
        currentLength++;
      }
      
      maxLength = Math.max(maxLength, currentLength);
      
      // Если нашли последовательность, которая включает больше половины элементов,
      // это, вероятно, максимальная последовательность
      if (currentLength > numSet.size / 2) {
        return currentLength;
      }
    }
  }
  
  return maxLength;
}

Оптимизация с использованием двух проходов

function longestConsecutive(nums) {
  if (nums.length === 0) return 0;
  
  const numSet = new Set(nums);
  let maxLength = 0;
  
  // Первый проход: находим все возможные начала последовательностей
  const sequenceStarts = [];
  for (const num of numSet) {
    if (!numSet.has(num - 1)) {
      sequenceStarts.push(num);
    }
  }
  
  // Второй проход: вычисляем длины последовательностей
  for (const start of sequenceStarts) {
    let currentNum = start;
    let currentLength = 1;
    
    while (numSet.has(currentNum + 1)) {
      currentNum++;
      currentLength++;
    }
    
    maxLength = Math.max(maxLength, currentLength);
  }
  
  return maxLength;
}

Почему оптимальное решение работает за O(n)?

На первый взгляд, может показаться, что вложенный цикл while в решении с хеш-множеством даёт временную сложность O(n²). Однако, важно понять, что:

Мы запускаем поиск последовательности только для чисел, которые являются началом последовательности (для которых num-1 не существует в множестве).
Для каждого элемента мы проходим по его последовательности только один раз. После того как мы обработали последовательность начинающуюся с числа x, мы никогда не будем снова проходить по тем же элементам в других итерациях.
В итоге, каждый элемент массива обрабатывается максимум дважды: один раз при добавлении в множество и один раз при проверке в цикле while.

Таким образом, общая временная сложность составляет O(n).

Заключение

При решении задачи важно помнить:

🤹‍♂️ Требование о линейной сложности O(n) исключает использование сортировки
📊 Хеш-множество (Set) - ключевая структура данных для эффективного решения
🧠 Оптимизация за счет проверки только начал последовательностей - важный аспект

Эта задача отлично демонстрирует, как правильный выбор структуры данных и оптимизация алгоритма позволяют достичь линейной временной сложности даже для задач, которые на первый взгляд требуют сортировки или более сложных подходов. 🌟

Попробуй решить популярные задачи

Массивы и Хеширование