Два указателя

Представьте две очереди, каждая к своему окошку. В каждой люди стоят по номерам талонов, от меньшего к большему. Одно окошко закрывают, и обе очереди нужно свести в одну, тоже по номерам.

Перестраивать всех заново не нужно. Достаточно смотреть на первых людей в обеих очередях и пропускать вперёд того, у кого номер меньше. Каждый человек проходит один раз, и новая очередь сразу получается по порядку.

В программе такие очереди — два отсортированных массива. Объединение их в один, тоже отсортированный, называют слиянием. Самый короткий способ — склеить массивы и отсортировать результат методом sort:

const a = [1, 3, 6, 8];
const b = [2, 3, 8];
const all = [...a, ...b].sort((x, y) => x - y);
console.log(all.join(" ")); // 1 2 3 3 6 8 8

Давайте разберём строку с sort:

1. [...a, ...b] раскладывает оба массива в один новый: [1, 3, 6, 8, 2, 3, 8].
2. sort((x, y) => x - y) упорядочивает его по возрастанию.
3. all.join(" ") печатает 1 2 3 3 6 8 8.

Результат верный, но sort рассчитан на числа в любом порядке. Язык не обещает, что метод воспользуется тем, что a и b уже отсортированы. Без этого знания сортировка длинного массива делает заметно больше сравнений, чем в нём чисел, а слиянию хватает не больше одного сравнения на каждое число.

Слияние отсортированных массивов часто дают на собеседовании. Ответ «склеить и отсортировать» там обычно не устраивает: ждут решения одним проходом по обоим массивам.

Два индекса

Метод двух указателей — проход по данным двумя индексами, каждый из которых сдвигается отдельно. Указатель здесь — обычная переменная с номером элемента. В очередях это палец, который вы держите на первом ещё не прошедшем человеке.

Шаг слияния

При слиянии индекс i идёт по a, а индекс j — по b. На каждом шаге:

1. Сравнивают a[i] и b[j].
2. Меньшее из двух чисел уходит в результат.
3. Сдвигается только индекс этого числа.

При равенстве можно взять любое из двух, но здесь берётся a[i]. Для массивов из примера выше шаги такие:

Хвост массива

После шестого шага массив a закончился, а в b осталось 8. Такой хвост уже отсортирован и не меньше всего, что попало в результат. Поэтому его дописывают в массив результата out целиком: out.push(...b.slice(j)).

Какой массив закончится первым, зависит от данных. Поэтому после цикла дописывают оба хвоста, a.slice(i) и b.slice(j): пустой ничего не добавит.

Здесь аналогия с очередями заканчивается. Люди из очереди уходят, а числа в a и b остаются на месте: движутся только индексы, и сами массивы слияние не меняет.

Каждый шаг отправляет в результат одно число, поэтому слияние массивов длиной n и m занимает не больше n + m шагов.

Общие элементы

Тем же проходом находят числа, которые есть в обоих отсортированных массивах:

const common = [];
let i = 0;
let j = 0;
while (i < a.length && j < b.length) {
    if (a[i] < b[j]) {
        i++;
    } else if (a[i] > b[j]) {
        j++;
    } else {
        common.push(a[i]);
        i++;
        j++;
    }
}
console.log(common.join(" ")); // 3 8

Давайте разберём, почему цикл устроен именно так:

• Цикл идёт, пока оба индекса внутри своих массивов.
• Меньшее число не встретится дальше в другом массиве: там стоят только числа больше. Поэтому индекс меньшего числа сдвигается.
• Из двух равных чисел одно попадает в результат, и сдвигаются оба индекса.

Нажимайте «Следующий шаг» и следите за i и j: на каждом шаге сдвигается индекс меньшего числа, а на равных — оба.

Для этих массивов цикл делает 5 шагов, а сравнение каждого числа из a с каждым числом из b заняло бы 12.

Частая ошибка

Хвост массива передали в push без трёх точек:

const out = [1, 2, 3];
const rest = [7, 9];
out.push(rest); // ✗
console.log(out.length);

Ошибки нет, но программа печатает 4, а не 5. Метод push получил один аргумент — массив — и положил его в out целиком, одним элементом. Синтаксис расширения раскладывает хвост на отдельные числа: out.push(...rest).

Главное

• Слияние двух отсортированных массивов идёт одним проходом двумя индексами, без sort.
• На каждом шаге в результат уходит меньшее число, и сдвигается только его индекс.
• После цикла дописывают оба хвоста: a.slice(i) и b.slice(j).
• Массив передают в push с тремя точками, иначе он ляжет в результат одним элементом.