Алгоритмы с нуля
Приём «видел»
Представь, что тебе дан массив [5, 2, 9, 11] и спрашивают: есть ли два числа, которые в сумме дают 14? Наивный подход: для каждого числа отсканируй остаток массива и посмотри, есть ли его дополнение. Это O(n²). Но вот ключевая идея: когда ты проходишь массив один раз, храни множество чисел, которые ты уже видел. Для каждого нового числа x проверь, есть ли (target - x) в множестве. Если да — ты нашёл пару. Если нет — добавь x в множество. Один проход, O(n) время. Это приём «видел», и он превращает множество O(n²) сканирований в один O(n) проход.
После этого урока ты можешь использовать множество «видел» для решения two-sum на неотсортированном массиве за O(n), понять, почему приём «видел» превращает вложенные циклы в один проход, обнаружить дубликаты с помощью множества «видел», найти пересечение двух массивов, обнаружить цикл в связном списке через вспоминание посещённых узлов, и узнать форму: «видел ли я что-то, что завершает ответ?» — храни по дороге, проверяй по дороге.
Проблема, которую мы решаем:
Тебе дан массив [5, 2, 11, 9] и целевая сумма 14. Найди два числа, которые в сумме дают 14.
Один подход: вложенные циклы.
function twoSumNaive(arr, target) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === target) {
return [i, j]; // Вернуть индексы
}
}
}
return null; // Пара не найдена
}Это O(n²): для каждого элемента ты сканируешь остаток массива. Для больших входов это медленно.
Идея приёма «видел»:
Вместо этого пройди массив один раз. По дороге храни множество чисел, которые ты видел до сих пор. Для каждого числа x спроси: есть ли (target - x) в множестве? Если да — ты нашёл пару и готов. Если нет — добавь x в множество и продолжи.
function twoSumSeen(arr, target) {
const seen = new Set();
for (let num of arr) {
const complement = target - num;
// Видел ли я дополнение раньше?
if (seen.has(complement)) {
return [complement, num]; // Нашли пару
}
// Нет, поэтому добавь это число в множество и продолжи
seen.add(num);
}
return null; // Пара не найдена
}Один цикл, O(n) время. Одно множество, O(n) память. Множество позволяет проверить «видел ли я X?» за O(1).
Почему это работает:
- Первый элемент: добавь его в множество.
- Второй элемент: проверь, есть ли его дополнение в множестве. Если да, готово. Если нет, добавь его.
- Третий элемент и далее: та же логика.
Потому что множество хранит все элементы, видённые до сих пор, и проверка принадлежности множеству это O(1), общее время это O(n) с одним проходом.
Форма приёма «видел»:
Приём имеет форму: храни по дороге, проверяй по дороге.
- Итерируй через данные.
- Для каждого элемента спроси: «видел ли я что-то, что завершает ответ?»
- Если да, ты нашёл.
- Если нет, запомни этот элемент и продолжи.
Эта форма работает для:
- Two-sum: видел ли я дополнение?
- Обнаружение дубликатов: видел ли я это значение раньше?
- Пересечение: видел ли я этот элемент в первом массиве?
- Первый дубликат: видел ли я это значение раньше (вернуть его)?
- Обнаружение цикла: посещал ли я этот узел раньше?
Two-sum компромисс: хеш-карта против двух указателей.
Если массив неотсортирован, приём «видел» (хеш-карта) это O(n) время, O(n) память.
Если массив отсортирован, приём двух указателей это O(n) время, O(1) память — без дополнительной памяти. Но сортировка неотсортированного массива занимает O(n log n), что медленнее хеширования.
Выбирай приём «видел» для неотсортированных данных. Выбирай двух указателей для отсортированных данных.
1. Two-sum с хеш-картой (вернуть индексы):
function twoSum(nums, target) {
const map = new Map(); // значение → индекс
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
// Видел ли я дополнение раньше?
if (map.has(complement)) {
return [map.get(complement), i]; // Вернуть два индекса
}
// Нет, поэтому сохрани это число и его индекс
map.set(nums[i], i);
}
return null; // Пара не найдена
}
const result = twoSum([2, 7, 11, 15], 9);
console.log(result); // [0, 1]2. Обнаружить первый дубликат с помощью множества «видел»:
function findFirstDuplicate(arr) {
const seen = new Set();
for (let num of arr) {
if (seen.has(num)) {
return num; // Нашли первый дубликат
}
seen.add(num);
}
return null; // Дубликатов нет
}
console.log(findFirstDuplicate([1, 2, 3, 2, 4])); // 2
console.log(findFirstDuplicate([1, 2, 3, 4])); // null3. Найти пересечение двух массивов:
function intersection(arr1, arr2) {
const set1 = new Set(arr1);
const result = new Set();
// Для каждого элемента в arr2, проверь, был ли он в arr1
for (let num of arr2) {
if (set1.has(num)) {
result.add(num); // Добавь в результат (избегни дубликатов множеством)
}
}
return Array.from(result);
}
console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]
console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [9, 4] или [4, 9]Попробуй пример two-sum:
Давай проследим приём two-sum на [2, 7, 11, 15] с target 9:
1
function twoSum(nums, target) {
2
const map = new Map();
3
for (let i = 0; i < nums.length; i++) {
4
const complement = target - nums[i];
5
if (map.has(complement)) {
6
return [map.get(complement), i];
7
}
8
map.set(nums[i], i);
9
}
10
return null;
11
}
Заметь: мы нашли пару на втором элементе, без цикла назад. Карта хранит индекс первого элемента, и мы проверяем его мгновенно через O(1) поиск.
Приём «видел»:
| Операция | Время | Память |
|---|---|---|
| Two-sum (хеш-карта) | O(n) | O(n) |
| Обнаружить первый дубликат | O(n) | O(n) |
| Найти пересечение | O(n + m) | O(n) |
| Обнаружить цикл (связный список) | O(n) | O(n) |
Где n и m это размеры входных данных.
Сравнение: вложенные циклы против приёма «видел»:
- Вложенные циклы: для каждого элемента сканируй остаток. n × n = O(n²).
- Приём «видел»: один цикл, O(1) поиски. O(n).
Для n = 1000, вложенные циклы: 1 000 000 операций. Приём «видел»: 1000. Разница растёт быстро.
Почему O(1) поиск важен:
В задаче two-sum проверка дополнения должна быть мгновенной. Если ты ищешь линейно (O(n) на проверку), общая сложность была бы O(n²) снова. Хеш-карты дают O(1) поиск, что существенно.
Почему приём «видел» решает two-sum за O(n) вместо O(n²)?
В two-sum, почему мы храним значение и его индекс в карте, а не просто добавляем в множество?
Если ты используешь приём «видел» чтобы найти первый дубликат в [1, 2, 3, 2, 4], какое число возвращается?
Для неотсортированных данных, какой лучше — приём «видел» (хеш-карта) или двух указателей, и почему?
Если ты проверяешь дубликаты в массиве из 5000 элементов используя приём «видел», сколько хеш-операций (добавь/проверь) ты выполняешь (примерно)?
lesson.inset.misconception
«Приём «видел» только для two-sum.» Неправда. Приём «видел» работает для любой задачи, где ты спрашиваешь «видел ли я это раньше?» — обнаружение дубликатов, пересечение, обнаружение цикла, поиск первого повторяющегося элемента, и много другого. Форма универсальна: храни по дороге, проверяй по дороге.
Граничные случаи
Пустой или одноэлементный вход: Пустой массив не имеет пар, поэтому вернуть null. Одноэлементный массив не может иметь пару с другим элементом, поэтому вернуть null. Всегда проверяй эти случаи.
Target недостижим: Если ни одна пара не суммируется в target, цикл завершается и ты возвращаешь null. Множество содержит все элементы, но ни один не образует пару.
Почему приём «видел» это O(n), а вложенные циклы это O(n²)?
Приём «видел» это практика хранения значений, которые ты встретил, в хеш-множестве или карте, когда ты проходишь данные, затем мгновенной проверки, видел ли ты что-то раньше.
Ключевые факты:
- Храни по дороге, проверяй по дороге: для каждого элемента проверь, есть ли он (или его дополнение) в множестве. Если да, ты нашёл ответ. Если нет, добавь его и продолжи.
- Временная сложность: O(n) потому что ты итерируешь один раз и каждая проверка это O(1).
- Пространственная сложность: O(n) потому что множество хранит до n значений.
- Частые применения:
- Two-sum: видел ли я дополнение?
- Обнаружение дубликатов: видел ли я это значение?
- Пересечение: видел ли я это в первом массиве?
- Первый дубликат: видел ли я это раньше?
- Обнаружение цикла: посещал ли я этот узел?
- Заменяет O(n²): наивный подход вложенных циклов. Приём «видел» решает за один проход.
- Меняем память на скорость: O(n) память покупает O(n) время вместо O(n²).
Теперь у тебя есть мощный приём, который применяется ко множеству реальных задач. Дальше ты изучишь, как коллизии в хеш-функциях влияют на производительность, и глубже погрузишься в дизайн хеш-функций.