re:re:actable
Урок 044 минуты чтения

Как превращать brute force в оптимальное решение?

На этой странице
Кратко

Brute force - не стыдная ошибка, а стартовая точка. Чтобы оптимизировать решение, нужно найти повторную работу и заменить ее памятью, сортировкой, двумя указателями, окном, бинарным поиском, графом или DP.

Вопрос

Как превращать brute force в оптимальное решение?

Зачем начинать с brute force

Brute force помогает:

  • проверить понимание задачи;
  • получить правильный, пусть и медленный, baseline;
  • увидеть повторяющуюся работу;
  • объяснить интервьюеру путь мысли;
  • не зависнуть в поиске идеального решения.

Шаг 1. Напиши прямую идею словами

Задача:

Найти, есть ли два числа с суммой target.

Brute force:

Проверить каждую пару.

Код:

function hasPairBrute(nums: number[], target: number): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return true
    }
  }
 
  return false
}

Сложность:

Time: O(n^2)
Space: O(1)

Шаг 2. Найди повторную работу

Внутренний цикл каждый раз ищет:

target - nums[i]

Значит нам нужна быстрая проверка наличия числа.

Структура данных:

Set

Оптимизация:

function hasPair(nums: number[], target: number): boolean {
  const seen = new Set<number>()
 
  for (const num of nums) {
    const need = target - num
 
    if (seen.has(need)) {
      return true
    }
 
    seen.add(num)
  }
 
  return false
}

Сложность:

Time: O(n)
Space: O(n)

Мы обменяли память на скорость.

Частые способы оптимизации

Повторная работаОптимизация
Часто проверяем наличиеSet
Часто ищем значение по ключуMap
Считаем сумму диапазона много разPrefix sums
Перебираем все подмассивыSliding window, если окно contiguous
Ищем пару в отсортированном массивеTwo pointers
Ищем границу ответаBinary search
Повторяем рекурсивные подзадачиMemoization / DP
Проверяем зависимостиGraph
Каждый раз нужен minimumHeap
Много раз объединяем группыDSU

Пример: суммы диапазона

Brute force:

function rangeSumBrute(nums: number[], left: number, right: number): number {
  let sum = 0
 
  for (let i = left; i <= right; i++) {
    sum += nums[i]
  }
 
  return sum
}

Если запрос один, это нормально.

Если запросов много, мы повторяем суммирование. Нужны prefix sums.

function buildPrefix(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0)
 
  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i]
  }
 
  return prefix
}
 
function rangeSum(prefix: number[], left: number, right: number): number {
  return prefix[right + 1] - prefix[left]
}

Построение O(n), каждый запрос O(1).

Пример: рекурсия Fibonacci

Brute force:

function fib(n: number): number {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

Проблема: одинаковые значения считаются много раз.

Memoization:

function fib(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n
  if (memo.has(n)) return memo.get(n)!
 
  const value = fib(n - 1, memo) + fib(n - 2, memo)
  memo.set(n, value)
 
  return value
}

Сложность становится O(n).

Как понять, что оптимизация правильная

После оптимизации проверь:

  • дает ли она тот же результат, что brute force;
  • какие данные хранятся дополнительно;
  • не меняет ли она порядок элементов;
  • не нарушает ли условие задачи;
  • работает ли на edge cases;
  • какая новая time/space complexity.

Что важно помнить: частые ошибки

  • Сразу писать сложное решение и потерять корректность.
  • Оптимизировать без понимания повторной работы.
  • Улучшить time, но забыть про space.
  • Использовать сортировку, когда нужно вернуть исходные индексы.
  • Применить sliding window к задаче, где элементы не contiguous.
  • Применить greedy без доказательства.

Что отвечать на собеседовании?

Я начинаю с brute force, потому что он фиксирует корректную идею. Потом ищу повторную работу: повторный поиск, повторное суммирование, повторные подзадачи, повторный обход. После этого подбираю инструмент: Map, Set, prefix sums, sliding window, two pointers, binary search, heap, graph или DP. Обязательно называю trade-off: обычно оптимизация ускоряет время за счет дополнительной памяти или предварительной обработки.

Мини-шпаргалка

  • Brute force - baseline.
  • Повторный поиск -> Map/Set.
  • Повторная сумма -> prefix sums.
  • Contiguous subarray -> sliding window.
  • Sorted input -> two pointers/binary search.
  • Повторные подзадачи -> DP.
  • Min/max каждый шаг -> heap.
  • Всегда сравнивай time и space до/после.

Документация

Tech Interview Handbook: Coding interview techniques.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам