DSA: алгоритм двух указателей. Ознакомьтесь с пошаговым руководством.

Структуры данных и алгоритмы являются фундаментальными строительными блоками для каждого разработчика, поскольку они помогают эффективно решать сложные проблемы. Думаю, никто не откажется от того, что мы используем DSA если не каждый день, то всегда, когда сталкиваемся с какой-то проблемой, которую должен решать наш код. Однако не всегда бывает так, что при решении задачи мы сразу понимаем «О! Для этого есть отличный алгоритм», и на бесконечной вселенной, состоящей из плеяды кодовых баз, появляется еще одно созвездие, напоминающее велосипед. Совершенство было так близко, но мы просто не знали о его существовании. Вот почему я считаю, что мы должны больше знать о существующих алгоритмах и методах. За один день это может улучшить вашу производительность и решить — ясно. Одним из таких алгоритмов, который часто может оказаться полезным для разработчиков, является алгоритм двух указателей. В этой статье будет рассмотрен алгоритм двух указателей, его приложения и то, как он может упростить ваш код для более эффективного решения различных проблем.

Приложения и варианты использования

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

1. Нахождение пар значений в массиве, которые в результате различных комбинаций дают заданный целевой ориентир. Это может быть полезно в финансах, например, для определения потенциальных пар инвестиций, которые вместе принесут желаемую прибыль.
2. Удаление дубликатов из отсортированного массива. Метод двух указателей можно использовать для эффективного удаления дубликатов из отсортированного массива. Один указатель перемещается по массиву, а другой указатель отслеживает последний найденный уникальный элемент. Это может помочь очистить данные для дальнейшей обработки или анализа.
3. Самая длинная подстрока без повторяющихся символов: при обработке строк можно использовать алгоритм двух указателей, чтобы найти длину самой длинной подстроки без повторяющихся символов. Эту проблему можно найти в различных приложениях, таких как анализ текста, сжатие данных или сопоставление с образцом.
4. Задачи со скользящим окном: метод двух указателей часто используется для решения задач со скользящим окном, когда вам нужно что-то вычислить на основе подмассива (окна) фиксированного размера, который перемещается по заданному массиву. Примеры включают поиск максимальной или минимальной суммы подмассива заданного размера и определение самого длинного подмассива, удовлетворяющего определенному условию.
5. Реверсирование массива или строки. Вы можете использовать метод двух указателей, чтобы инвертировать элементы в массиве или символы в строке, поменяв местами элементы, на которые указывают два указателя, и переместив их друг к другу, пока они не встретятся посередине.
6. Проблемы с палиндромом: алгоритм двух указателей можно использовать для определения того, является ли строка палиндромом, сравнивая символы в начале и конце строки и перемещая указатели к центру. Кстати, эту проблему тоже можно решить методом «расширения вокруг центра».

Это всего лишь несколько примеров из многих проблем, которые может помочь решить метод двух указателей. Поняв концепцию и применив ее к различным ситуациям, вы сможете оптимизировать свой код и разработать более эффективные решения проблем, связанных с массивами и строками. N̶o̶ ̶m̶o̶r̶e̶ ̶b̶y̶c̶i̶c̶l̶e̶s̶.
В следующих разделах я не буду рассматривать все описанные примеры, но я подготовил 2 примера: общий и частный.

Пример пересечения отсортированных массивов

У вас есть два отсортированных массива целых чисел. Ваша задача найти пересечение этих двух массивов, а значит, вам нужно найти общие элементы в обоих массивах. Вот примеры этого алгоритма, реализованного в JavaScript, Python и Java:

function intersection(arr1, arr2) {
    const result = [];
    let i = 0;
    let j = 0;
    
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] === arr2[j]) {
            result.push(arr1[i]);
            i++;
            j++;
        } else if (arr1[i] < arr2[j]) {
            i++;
        } else {
            j++;
        }
    }
    
    return result;
}

const arr1 = [1, 2, 3, 4, 5];
const arr2 = [3, 4, 5, 6, 7];
const result = intersection(arr1, arr2);
console.log(result); // Output: [3, 4, 5]
def intersection(arr1, arr2):
    result = []
    i = 0
    j = 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] == arr2[j]:
            result.append(arr1[i])
            i += 1
            j += 1
        elif arr1[i] < arr2[j]:
            i += 1
        else:
            j += 1
            
    return result

arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
result = intersection(arr1, arr2)
print(result) # Output: [3, 4, 5]
public class ArrayUtils {
  public static List<Integer> intersection(int[] arr1, int[] arr2) {
      List<Integer> result = new ArrayList<>();
      int i = 0;
      int j = 0;
      
      while (i < arr1.length && j < arr2.length) {
          if (arr1[i] == arr2[j]) {
              result.add(arr1[i]);
              i++;
              j++;
          } else if (arr1[i] < arr2[j]) {
              i++;
          } else {
              j++;
          }
      }
      
      return result;
  }
}

int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 4, 5, 6, 7};
List<Integer> result = ArrayUtils.intersection(arr1, arr2);
System.out.println(result); // Output: [3, 4, 5]

Давайте подробнее рассмотрим этот пример. Для более удобного чтения ниже вы можете найти визуализацию выполнения.

Итак, что здесь произошло: мы определили два указателя i и j и результирующий массив.

Затем мы начали итерацию по обоим массивам. Если один из массивов короче, чем более, количество шагов будет равно самому длинному.
Наша цель — найти совпадающие значения в обоих массивах. Итак, давайте добавим еще один переменный счетчик для целей отладки.

step_counter = 1
while (i < arr1.length && j < arr2.length) {
    // bla bla bla
    ...
  step_counter++    
}

Первые две итерации просто увеличивают значение if i, потому что оно удовлетворяет условию while (i ‹ arr1.length && j ‹ arr2.length)

На третьем шаге мы встречаем еще одно соответствие условию if (arr1[i] == arr2[j]), что означает, что результирующий массив должен быть выполнен с совпадающим значением (3) в их свою очередь, i и j будут увеличены на +1.

Хорошо, мило. Мы убедились, что пересечение работает, и мы могли легко догадаться, что результатом будет [3,4,5]. Но для чего здесь этот блок после arr1[i] == arr2[j] и arr1[i] ‹ arr2[j]?

else {
  j++;
}

Давайте представим другие входы

arr1 = [4, 5, 8, 9, 10]
arr2 = [3, 4, 5, 6, 7, 10, 11]

Итак, очевидно, arr1[0] -> 4 и arr2[0] -> 3, 4 не равно 3 и 4 не меньше 3. Наша программа поймает бесконечный цикл.

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

Самая большая прямоугольная комната

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

Представьте, мы работаем над проектом, который помогает нашим пользователям создавать макеты домов на основе различных входных данных и конкретных условий. Пользователи предоставляют различные размеры комнат и размеров стен с возможностью создания макета, в котором самая большая комната является холлом. Такой индивидуальный подход позволяет создавать индивидуальные конструкции, отвечающие индивидуальным предпочтениям и требованиям. Итак, наша цель по заданному массиву длин стен и положительному целому числу n, представляющему количество стен, найти самую большую прямоугольную комнату, которую можно сформировать, используя любые две стены в качестве длины и ширины.

Итак, нам нужно найти какое-то решение, которое помогло бы нам вычислить любые комбинации длин стен и найти две из них и максимальную площадь. А также нам не нужно очень медленное и сложное решение.

Решение:

1. Инициализируйте два указателя, left и right, установив left в 0, а right в n - 1.
2. Пока left меньше right: a. Вычислите площадь прямоугольника, образованного длинами стен по указателям left и right. б. Отслеживайте максимальную площадь, найденную на данный момент. в. Сравните длину стены по указателям left и right и переместите указатель с меньшей длиной стены к центру.
3. Возвращает максимальную найденную площадь.

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

def largest_rectangular_room(wall_lengths):
    left = 0
    right = len(wall_lengths) - 1
    max_area = 0

    while left < right:
        area = min(wall_lengths[left], wall_lengths[right]) * (right - left)
        max_area = max(max_area, area)

        if wall_lengths[left] < wall_lengths[right]:
            left += 1
        else:
            right -= 1

    return max_area

wall_lengths = [2, 4, 19, 10, 11, 8]
print(largest_rectangular_room(wall_lengths))  # Output: 24
function largestRectangularRoom(wallLengths) {
    let left = 0;
    let right = wallLengths.length - 1;
    let maxArea = 0;

    while (left < right) {
        const area = Math.min(wallLengths[left], wallLengths[right]) * (right - left);
        maxArea = Math.max(maxArea, area);

        if (wallLengths[left] < wallLengths[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

const wallLengths = [5, 6, 8, 10, 12];
console.log(largestRectangularRoom(wallLengths));  // Output: 60
public class LargestRectangularRoom {
    public static int largestRectangularRoom(int[] wallLengths) {
        int left = 0;
        int right = wallLengths.length - 1;
        int maxArea = 0;

        while (left < right) {
            int area = Math.min(wallLengths[left], wallLengths[right]) * (right - left);
            maxArea = Math.max(maxArea, area);

            if (wallLengths[left] < wallLengths[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] wallLengths = {5, 6, 8, 10, 12};
        System.out.println(largestRectangularRoom(wallLengths));  // Output: 60
    }
}

На этот раз мы определили левую и правую части как первый и последний элементы данного массива.

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

min(wall_lengths[left], wall_lengths[right]) * (right - left)

Заключение

Надеюсь, вам понравилось погрузиться в этот алгоритм. И мое объяснение было для вас полезным.

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

Использованная литература:

https://algorithm-visualizer.org/
https://cscircles.cemc.uwaterloo.ca/visualize#

Код с трассировкой

const { Tracer, Array1DTracer, LogTracer, Layout, VerticalLayout } = require('algorithm-visualizer');

const arr1tracer = new Array1DTracer('Walls');
const resultTracer = new Array1DTracer('Result');
const logger = new LogTracer();

Layout.setRoot(new VerticalLayout([arr1tracer, resultTracer, logger]));

function largestRectangularRoom(wallLengths) {
    arr1tracer.set(wallLengths)
    Tracer.delay()
    
    let left = 0;
    let right = wallLengths.length - 1;
    let maxArea = 0;

    while (left < right) {
        arr1tracer.select(left)
        arr1tracer.select(right)
        Tracer.delay()
        
        const area = Math.min(wallLengths[left], wallLengths[right]) * (right - left);
        logger.println(`min(wallLengths[left], wallLengths[right]) ${Math.min(wallLengths[left], wallLengths[right])} * (right - left) ${(right - left)}`)
        maxArea = Math.max(maxArea, area);
        resultTracer.patch(0, maxArea)
        
        logger.println(`left ponter ${left} and right ${right}, maxArea ${maxArea}`)
        
        Tracer.delay()
        if (wallLengths[left] < wallLengths[right]) {
            arr1tracer.deselect(left)
            left++;
        } else {
            arr1tracer.deselect(right)
            right--;
        }
        Tracer.delay()
    }

    return maxArea;
}

const wallLengths = [2, 4, 19, 10, 11, 8];
console.log(largestRectangularRoom(wallLengths));