Алгоритмические задачи на JavaScript: 12 упражнений по шагам

Алгоритмические задачи на JavaScript полезно решать по одному циклу: уточнить вход и выход, придумать простой вариант, проверить крайние случаи, оценить сложность и только потом оптимизировать. Начните с массивов, строк, Map и Set, затем добавьте два указателя, стек, очередь, сортировку и бинарный поиск.

Задача не проверяет способность вспомнить красивый трюк. Она проверяет моделирование данных и аргументацию. В JavaScript массив является универсальной индексируемой коллекцией, Map хранит пары ключ-значение, Set поддерживает уникальность. Уточняйте, можно ли менять исходный массив, нужны ли индексы или значения, допустимы ли дубли и как обрабатывать отсутствие ответа.

Алгоритмические задачи на JavaScript: пара с заданной суммой

Нужно вернуть индексы двух разных элементов, сумма которых равна target. Двойной цикл прост, но требует квадратичного числа сравнений. Map позволяет за один проход хранить уже встреченные значения и искать дополнение target - value. До кода проговорите поведение при нескольких ответах: пример возвращает первую найденную пару.

function findPair(numbers, target) {
  const seen = new Map();

  for (let index = 0; index < numbers.length; index += 1) {
    const value = numbers[index];
    const needed = target - value;

    if (seen.has(needed)) {
      return [seen.get(needed), index];
    }

    // Сохраняем индекс уже просмотренного значения
    seen.set(value, index);
  }

  return null;
}

console.log(findPair([2, 7, 11, 15], 9)); // [0, 1]

Время работы в среднем линейно по числу элементов при обычном поведении Map, память тоже линейна в худшем случае. Проверьте [3, 3] с target 6: первый индекс уже лежит в Map, когда обход доходит до второго элемента. Проверьте пустой массив и отсутствие ответа. Если вход отсортирован и нужны значения, можно использовать два указателя без Map, но контракт должен позволять потерю исходных индексов или их отдельное сохранение.

12 задач в порядке роста

Для каждой задачи храните три версии: постановка, собственное решение и тесты. Не оптимизируйте до рабочего простого варианта. Сортировка может упростить алгоритм, но стоит O(n log n) и иногда меняет исходный массив. Метод sort без comparator сортирует значения как строки, поэтому для чисел используйте (a, b) => a - b. Это частый источник неожиданных результатов.

Практика: соберите two sum на Map и проверьте крайние случаи

Создайте файл findPair.js и перенесите в него функцию из статьи вместе с пятью вызовами console.log. Успехом считайте такой прогон: findPair([2, 7, 11, 15], 9) возвращает [0, 1], а вход без ответа возвращает null. Задача закрыта, когда вы можете вслух назвать число проходов по массиву и объём памяти под Map.

Переставьте seen.set(value, index) выше проверки seen.has(needed) и снова запустите findPair([3, 3], 6). Функция вернёт [0, 0], то есть сложит элемент сам с собой: значение попадает в Map раньше, чем ищется дополнение. Второй излом сделайте на сортировке: вызовите [10, 9, 100].sort() без comparator и посмотрите на [10, 100, 9], где 100 стоит перед 9 из-за сравнения строк. Верните обе строки как было и убедитесь, что [0, 1] и числовой порядок вернулись.

Дальше решите ту же пару с заданной суммой двумя указателями на отсортированном массиве: сумма больше target - двигаете правую границу, меньше - левую, дополнительная память не нужна. Сравните контракты: версия с указателями отдаёт значения, а исходные индексы теряются после сортировки. Потом идите по списку из 12 задач в его порядке: частоты через Map, палиндром и скобки через стек, затем бинарный поиск. Для каждой задачи храните три файла: постановку, своё решение и тесты.

Частые ошибки и почему они появляются

Копирование решения после двух минут лишает задачу главной пользы. Вторая ошибка: назвать O(n), не определив n и операции. Третья: проверить только пример из условия. Рабочая подготовка требует написать тесты до просмотра чужого решения и вернуться к задаче через несколько дней без подсказки.

Самопроверка