Добро пожаловать обратно в нашу серию блогов, посвященную решению проблем в современной разработке программного обеспечения!

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

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

02. Шаблон с несколькими указателями

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

Пример задачи

Напишите функцию под названием sumZero, которая принимает отсортированный массив целых чисел. Функция должна найти первую пару, где сумма равна нулю. Если такая пара существует, верните массив, включающий оба значения; в противном случае верните неопределенное.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Базовое решение

function sumZero(arr){
    for (let i = 0; i 



Временная сложность - O(N^2)

Решение с использованием шаблона многоуказателя

Шаг 1. Поймите проблему

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

шаг 2. Инициализация двух указателей

Установите два указателя: один (left), начиная с начала массива, и другой (right), начиная с конца.

Пример:


Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5




Шаг 3. Вычислите сумму значений указателей

Сложите значения левого и правого указателей, чтобы получить сумму


Sum = -4   5 = 1




Шаг 4. Сравните сумму с нулем

• Если сумма больше нуля: Переместите правый указатель на один шаг влево, чтобы уменьшить сумму.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• Если сумма меньше нуля: Переместите левый указатель на один шаг вправо, чтобы увеличить сумму.

New Sum = -4   2 = -2
Sum is -2 



Шаг 5. Повторите процесс

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


New Sum = -3   2 = -1
Sum is -1 



Сумма равна нулю, поэтому функция возвращает [-2, 2].

Если цикл завершается и такая пара не найдена, верните undefined.

Окончательный код


function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left  0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left  ;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}




ПРИМЕЧАНИЕ:
Временная сложность: O(n) — функция эффективна и линейно масштабируется в зависимости от размера массива.
Пространственная сложность: O(1) — функция использует минимальный объем дополнительной памяти.

Заключение

Шаблон многоуказателя — это мощный метод решения задач, связанных с поиском, сравнением или манипулированием элементами в отсортированной структуре данных. Используя несколько указателей, которые движутся навстречу друг другу, мы можем значительно повысить эффективность алгоритмов, во многих случаях уменьшая временную сложность с O(n²) до O(n). Этот шаблон универсален и может применяться к широкому кругу задач, что делает его важной стратегией оптимизации производительности вашего кода.

Ждите нашей следующей статьи, где мы углубимся в Шаблон скользящего окна еще один важный инструмент для решения проблем, связанных с динамическими сегментами данных. Это невероятно полезный шаблон, который поможет вам с легкостью решать даже более сложные задачи!