Алгоритмы с нуля
Массивы и строки: чтение кода
Суть Читай реальные сниппеты на two pointers, sliding window, prefix sum и in-place, затем предскажи вывод, назови сложность или найди баг, который поймает тест.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеПриём легко проговорить и легко сломать. Читай каждый сниппет как на ревью: проследи указатели, проверь границу и реши, делает ли цикл то, что думает его автор.
Цель
Потренируй чтение приёмов юнита в коде — предсказание вывода, точную сложность и поиск off-by-one или отсутствующего предусловия до того, как это уйдёт в прод.
Сниппет 1 — вариативное окно
function minSubarrayLen(arr, target) {
let left = 0, sum = 0, best = Infinity;
for (let right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= arr[left];
left++;
}
}
return best === Infinity ? 0 : best;
}
// minSubarrayLen([2, 3, 1, 2, 4, 3], 7) Викторина
Completed
Что вернёт этот вызов и какова временная сложность алгоритма?
Heads-up [4, 3] = 7 даёт длину 2, что лучше [1, 2, 4]. И это O(n): left движется только вперёд за весь прогон, поэтому внутренний цикл амортизирован по n суммарным сдвигам — не O(n²).
Heads-up Несколько подмассивов достигают 7 — например [4, 3]. Функция возвращает 0 только когда ни одно окно не подходит, а здесь это не так.
Heads-up Длина верна, но Math.min — O(1), и здесь нет ни сортировки, ни деления пополам. Оценка O(n) идёт из движения указателей только вперёд.
Сниппет 2 — уплотнение in-place
function removeVal(arr, val) {
let write = 0;
for (let read = 0; read < arr.length; read++) {
if (arr[read] !== val) {
arr[write] = arr[read];
write++;
}
}
return write;
}
// const a = [3, 2, 2, 3]; const k = removeVal(a, 3); Викторина
Completed
После вызова — чему равно k и каково состояние первых k ячеек a?
Heads-up Техника write-указателя не очищает хвост; она гарантирует только, что a[0..k-1] — это сохранённые значения. В хвостовых ячейках остаётся то, что туда записали последним, и их нужно игнорировать.
Heads-up k — это write-указатель, а не счётчик итераций. Он сдвигается только когда arr[read] !== val, поэтому в конце равен 2 — числу сохранённых элементов.
Heads-up Условие сохраняет элементы, НЕ равные val, поэтому 3 отбрасываются, а 2 сохраняются. a[0..1] = [2, 2].
Сниппет 3 — two-sum с концов
function twoSum(arr, target) {
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
else if (sum < target) left++;
else right--;
}
return null;
}
// twoSum([8, 2, 5, 1, 7], 9) Викторина
Completed
Массив [8, 2, 5, 1, 7] не отсортирован. Корректная пара с суммой 9 существует (8 + 1 или 2 + 7). Что этот код реально вернёт и почему?
Heads-up Проследи: 8 + 7 = 15 > 9 → right-- ; 8 + 1 = 9 → вернёт [0, 3]. Он возвращает пару по удаче. Реальный урок — корректность не гарантирована на неотсортированном входе.
Heads-up Условие цикла left < right не даёт указателям пересечься; цикл выходит чисто и возвращает null, если пара не найдена. Исключения нет.
Heads-up Two pointers не даёт такой гарантии порядка на неотсортированных данных. Проследив этот вход, он доходит до 8 + 1 = 9 и возвращает [0, 3] — а на других входах может пропустить пару вовсе.
Сниппет 4 — запрос суммы на диапазоне через prefix sum
function buildPrefix(arr) {
const p = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) p[i + 1] = p[i] + arr[i];
return p;
}
function rangeSum(p, i, j) { return p[j] - p[i - 1]; }
// const p = buildPrefix([2, 5, 1, 3, 4]); // p = [0, 2, 7, 8, 11, 15]
// rangeSum(p, 1, 3) // задумано: arr[1] + arr[2] + arr[3] = 9 Викторина
Completed
buildPrefix корректна, но в rangeSum есть off-by-one. Что вернёт rangeSum(p, 1, 3) и какой фикс?
Heads-up Подставь: p[3] − p[0] = 8 − 0 = 8, а не 9. Индексы сдвинуты на один, потому что p[k] суммирует первые k элементов — запросу нужно p[j+1] − p[i].
Heads-up p[0] определён и равен 0 — buildPrefix его заполняет. Краша нет; баг — тихий неверный ответ 8 из-за рассогласованной индексации.
Heads-up Prefix sum не недосчитывает систематически; формула просто должна соответствовать конвенции. Здесь p[3] − p[0] = 8; фикс — p[j+1] − p[i] = 9.
Итог
Чтение приёмов в коде — там, где прячутся баги. Вариативное окно — O(n), потому что left движется только вперёд: внутренний while амортизирован, а не вложен. Уплотнение in-place гарантирует только a[0..k-1]; хвост устарел по контракту. Two-sum с концов несостоятелен на неотсортированном входе, даже когда случайно возвращает пару. А запросы prefix sum живут или умирают на конвенции n+1: p[k] — сумма первых k элементов, поэтому формула диапазона — p[j+1] − p[i]. Проследи указатели и проверь границу, прежде чем доверять циклу.