Два указателя — это метод, используемый для решения задач с массивами и строками. Одним из преимуществ использования метода двух указателей является то, что цикл while никогда не будет иметь более O(n) итераций. В большой нотации O O(n) или линейная сложность описывает производительность алгоритма, время выполнения которого будет расти линейно и прямо пропорционально размеру входных данных.

Техника двух указателей состоит в создании двух целочисленных переменных, которые перемещаются по итерируемому объекту. Эти переменные, обычно называемые i и j, представляют собой два индекса массива или входной строки. Существует множество различных способов реализации двух указателей. Мы рассмотрим одну технику в следующем примере.

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

var arr = [‘h’, ‘e’, ‘l’, ‘l’, ‘o’]

const reverseArray = (arr) => {
  // assign the two pointers to the first and last index
  let i = 0;
  let j = arr.length-1;

  while (i < j) {
    let tmp = arr[i]; // statement 1
    arr[i++] = arr[j]; // statement 2
    arr[j--] = tmp; // statement 3
  };

  return arr;
};

Сначала мы присваиваем переменной i индекс 0 и j последнему индексу входной строки arr.length-1. Мы используем i < j для условия проверки цикла while. Пока это условие истинно, цикл while будет выполнять свои операторы. Помните, что с while циклами условие всегда оценивается до выполнения оператора.

Для каждой итерации мы выполняем три оператора:

  1. Назначьте tmp на arr[i]. Это позволяет нам переназначить arr[i] во втором операторе и по-прежнему иметь возможность присвоить исходное значение arr[i] arr[j].
  2. Присвойте arr[i] значению arr[j] и увеличьте i на 1
  3. Присвойте arr[j] значению tmp и уменьшите j на 1

Первая итерация в этом примере меняет местами arr[0] («h») на arr[3] («o»). Вторая итерация меняет местами arr[1] («e») на arr[2] («l») и так далее. Поскольку мы не создавали новый массив, нам просто нужно вернуть измененный arr, который был перевернут.

В этом примере функция reverseArray изменяет исходный массив на месте, что дает нам пространственную сложность O(1). В нотации Big O, сложность пространства O(1) или постоянное пространство означает, что алгоритм использует один и тот же объем памяти независимо от размера входных данных.