Массивы и строки

Массив — непрерывный блок памяти с O(1) доступом по индексу: адрес = base + i · sizeof(element). Это даёт мгновенный random access и отличную работу с CPU cache (последовательное чтение — самое быстрое в железе). Строка — массив символов, но в JS она immutable: любое изменение создаёт новую строку. Массивы и строки лежат в основе 80% задач на алгоритмических собесах: от Two Sum до Kadane.

Когда применять / Мотивация

Массив — первый кандидат, когда нужна коллекция с доступом по индексу или последовательной обработкой. Если паттерн — random access, обход слева направо, диапазонные запросы — массив выигрывает у связного списка за счёт кеш-локальности. На собесах массивы появляются в задачах:

поиск подмассива с условием (sliding window);
сортировка / выбор k-го элемента;
два указателя (Two Sum, container with most water);
prefix sums для range queries;
difference arrays для range updates.

В реальных системах: обработка логов, network buffers, изображения (2D массивы), time-series, batch processing. Senior знает, что выбор «массив vs список» зависит от паттерна доступа: random access → массив, частые вставки в середину → список (но кеш всё равно часто делает массив быстрее).

Идея / Как работает

Массив: O(1) доступ, O(n) вставка/удаление в середину (нужен сдвиг). Динамический массив (JS array, ArrayList) удваивает capacity при переполнении — отсюда amortized O(1) для push.

Строка в JS: UTF-16 code units. Emoji может занимать 2 code units, поэтому str.length — это число code units, а не символов. Для подсчёта grapheme clusters нужен Intl.Segmenter.

Конкатенация в цикле — главная ловушка строк:

// ПЛОХО — O(n²): каждый += создаёт новую строку
let s = '';
for (let i = 0; i < n; i++) s += 'x';

// ХОРОШО — O(n): массив + join
const parts: string[] = [];
for (let i = 0; i < n; i++) parts.push('x');
const s = parts.join('');

Базовые техники для массивов:

Two pointers — два индекса сходятся/расходятся (Two Sum в отсортированном, palindrome check).
Sliding window — окно фиксированной/переменной длины (substring problems).
Prefix sums — препроцессинг O(n), потом range sum за O(1).
Hash map seen-set — запоминаем встреченные элементы для O(1) lookup.

Реализация

Two Sum через Hash Map

Вход: nums = [2, 7, 11, 15], target = 9. Выход: [0, 1].

Идея: один проход. Для каждого nums[i] ищем complement = target - nums[i] в map. Если есть — нашли пару, иначе сохраняем nums[i].

function twoSum(nums: number[], target: number): [number, number] | null {
  const map = new Map<number, number>(); // число → его индекс
  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;
}

Префиксные суммы (Range Sum Query)

Препроцессинг O(n), потом любой sum(arr[l..r]) за O(1):

function buildPrefix(arr: number[]): number[] {
  const prefix = [0]; // prefix[0] = 0 (пустой префикс)
  for (const x of arr) {
    prefix.push(prefix[prefix.length - 1] + x);
  }
  return prefix; // prefix[i] = sum(arr[0..i-1])
}

const rangeSum = (prefix: number[], l: number, r: number): number =>
  prefix[r + 1] - prefix[l];

Kadane — максимальный подмассив

Классический O(n) для поиска подмассива с наибольшей суммой:

function maxSubArray(nums: number[]): number {
  let maxSoFar = nums[0];
  let maxEndingHere = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // Либо начать новый подмассив с nums[i], либо продолжить текущий
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

Трассировка Two Sum

nums = [2, 7, 11, 15], target = 9, map = {}
i=0: nums[0]=2, complement=7, map не содержит 7
     → map.set(2, 0)        map = {2 → 0}
i=1: nums[1]=7, complement=2, map содержит 2!
     → return [0, 1]

Результат: [0, 1] (2 + 7 = 9) ✓

Ключевой момент: проверяем complement до добавления текущего числа в map. Иначе на [5] с target=10 вернули бы [0, 0] — невалидно.

Сложность

Операция	Время	Память	Объяснение
Two Sum (hash)	O(n)	O(n)	Один проход, O(1) на map
Two Sum (sort + 2ptr)	O(n log n)	O(n)	Сортировка с сохранением индексов
Build prefix sums	O(n)	O(n)	Один проход
Range sum query	O(1)	—	Просто разность
Kadane	O(n)	O(1)	Один проход, две переменные

Hash O(n) — оптимум для Two Sum: мы обязаны прочитать все элементы.

Типичные ошибки и подводные камни

arr.sort() без компаратора: лексикографически. [10, 2, 20].sort() → [10, 2, 20]. Всегда: arr.sort((a, b) => a - b).
Конкатенация строк s += 'x': O(n²). Используйте массив + join('').
Использование одного индекса дважды: в Two Sum проверка complement до записи защищает от этого.
Дубликаты в map: [2, 7, 2, 11], target=9. Второй 2 перезапишет первый — но это не проблема, потому что хотя бы один 2 уже там, когда встретим 7.
UTF-16 в JS: '😀'.length === 2. Для итерации по code points используйте for...of или Array.from(str).
Sparse arrays: arr[1000] = 1 в пустом массиве убивает оптимизацию V8.
Out-of-bounds access: arr[arr.length] — undefined, не exception. Проверяйте границы вручную в алгоритмах.

Follow-up вопросы интервьюера

Можно ли решить Two Sum без доп. памяти? Сортируем + two pointers: O(n log n) времени, O(1) памяти (если сортируем in-place). Но теряем исходные индексы — нужны пары [value, index], опять O(n) памяти.
Все уникальные пары с суммой target. Сортируем, two pointers, при нахождении — пропуск дубликатов: while (left < right && nums[left] === nums[left+1]) left++;
Three Sum (a + b + c = 0). Сортируем, фиксируем nums[i], для подмассива применяем two sum. O(n²).
Two Sum в потоке. Hash set всех увиденных: при поступлении x проверяем target - x в set. O(1) на операцию, O(n) памяти.
Массив не влезает в RAM. External merge sort + two pointers по блокам с диска. Или streaming hash, если уникальных значений мало.
Подсчёт количества пар. Hash map value → count. Для каждого x прибавляем map.get(target - x). Если x === target/2 — особый случай: C(count, 2) = count·(count-1)/2.
Subarray Sum Equals K. Prefix sum + hash map: Map<prefixSum, count>. Для каждого prefix[i] ищем prefix[i] - K. O(n).
Container With Most Water. Two pointers с обоих концов, двигаем меньший. O(n).

Чеклист на собес

Уточнил: отсортирован ли массив, есть ли дубликаты, диапазон значений.
Знаю trade-off hash O(n)/O(n) vs two pointers O(n log n)/O(1).
Помню про (a, b) => a - b в sort.
Не использую += для строк в цикле — массив + join.
Проверяю границы массива и пустой ввод.
Знаю шаблоны: two pointers, sliding window, prefix sums, Kadane.
Помню про UTF-16 при работе со строками с эмодзи.