Как превращать 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 |
| Каждый раз нужен minimum | Heap |
| Много раз объединяем группы | 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 до/после.