Не будет ошибкой сказать, что метод двух указателей является одним из самых важных инструментов в любом наборе разработчика программного обеспечения или даже для новичков это метод, который необходимо изучить, поскольку он поможет любому и каждому на протяжении всего пути и даже в их технические интервью. Мы поймем эту технику, задав себе три вопроса: что, почему, как ?.
Что представляет собой метод двух указателей?
Название (Два указателя) гласит, что мы используем в этом методе два указателя или маркера для перемещения на итерируемом списке / массиве для выполнения операций поиска с использованием двух указателей / маркеров в одном цикле в структурах данных, таких как списки / массивы, строки, связанные списки. Теперь поговорим о вариантах метода двух указателей:
- Противоположно-направленный: в этом случае каждый указатель / маркер размещается на противоположных концах массива, и они движутся навстречу друг другу при перемещении до тех пор, пока не встретятся или не будет выполнено какое-либо другое условие. Вопросы, основанные на этом варианте Два указателя:
- Равнонаправленный: в этом случае каждый указатель / маркер начинается с самого начала, один из которых является медленным, а другой - более быстрым, движется в том же направлении до тех пор, пока не будет выполнено определенное условие. Вопрос основан на этом варианте Two Pointer:
Почему используется метод двух указателей?
Наиболее очевидной причиной использования этого метода является уменьшение временной сложности задачи с O (n3) или O ( n2) до O (n) или O (nlogn) в зависимости от того, отсортирован массив или нет.
Как использовать технику двух указателей?
Давайте разберемся с этим, рассмотрев тот же вопрос, упомянутый выше: Две суммы (отсортированный массив) . Итак, проблема в следующем:
Given an array of integersnumbersthat is already sorted in non-decreasing order, find two numbers such that they add up to a specifictargetnumber.Return the indices of the two numbers (1-indexed) as an integer arrayanswerof size2, where1 <= answer[0] < answer[1] <= numbers.length. Example: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1,index2 = 2.
Из предыдущей проблемы мы можем сделать вывод, что нам дан отсортированный массив и число; мы должны пройти по массиву и найти два таких числа, которые в сумме дают указанное число, а затем вернуть индексы этих чисел. Теперь поговорим о подходах, которые можно использовать для решения этой проблемы:
1. Грубая сила | Сложность времени: O (n2)
2. Техника двух указателей | Сложность времени: O (n)
Первый подход очень прост по своей природе, но все же требует много времени. Я объясню их оба, чтобы указать на очевидное (временная сложность).
Подход грубой силы: при грубой силе мы используем два цикла: внешний цикл повторяется по каждому элементу один за другим, а внутренний делает то же самое, но для каждого отдельного перехода через элемент внешнего цикла внутренний цикл завершает всю итерацию массива. В этом подходе мы проверяем сумму каждого элемента массива с каждым другим элементом, а затем сравниваем ее с заданной суммой, проверяя на равенство. Код для этого же приведен ниже.
Метод двух указателей. В этом методе мы используем два указателя / маркера для обнаружения элементов в отсортированном массиве, которые в сумме дают желаемое значение. Мы начинаем с инициализации двух указателей, один до крайнего левого индекса: start = 0, а другой - до конца массива: end = length (array) -1. Теперь мы будем перебирать массив до тех пор, пока начало не станет меньше конца, а затем добавим элементы, на которые указывают указатели, чтобы проверить, соответствуют ли они требуемому номеру. Мы можем вернуть переменные начала и конца, если сумма равна числу; если сумма больше необходимого числа, мы уменьшаем конечную переменную на единицу; в противном случае мы увеличиваем начало на единицу. Поскольку массив отсортирован, мы можем воспользоваться тем фактом, что если мы уменьшим конец переменной, число, указанное им, будет меньше, чем число перед ним, уменьшая общую сумму и то же самое касается начала увеличения, оно увеличит общая сумма. Код для того же был прикреплен ниже.
АЛГОРИТМ РАЗДВИЖНОГО ОКНА
Итак, после алгоритма Two Pointer мы будем говорить об алгоритме Sliding Window, поскольку после метода двух указателей он также является одним из самых важных инструментов в любом разработчике программного обеспечения. комплект или даже для новичка, это метод, который необходимо изучить, поскольку он поможет любому и каждому на протяжении всего пути и даже во время технических собеседований. Мы поймем эту технику, задав себе три вопроса: что, почему, как ?.
Что такое алгоритм скользящего окна?
Проблемы, связанные с линейными последовательностями, такими как массивы, могут быть решены с использованием подхода скользящего окна. Непрерывная последовательность, являющаяся частью массива, называется окном. Окно скользит по массиву, как следует из названия. Окно сдвигается дальше, когда над элементами внутри него выполняются некоторые операции. Существуют различные варианты этого алгоритма, но мы не будем рассматривать их все в этой статье, так как в этой статье мы будем говорить о наиболее общем из существующих. Ниже приводится вопрос, в котором можно использовать этот алгоритм.
Почему используется алгоритм скользящего окна?
Этот алгоритм помогает нам, уменьшая временную сложность, как и алгоритм двух указателей, и большое количество вопросов и вариантов этого алгоритма. используются значительной частью сообщества разработчиков.
Как использовать алгоритм скользящего окна?
Давайте разберемся в этом, рассмотрев тот же вопрос, упомянутый выше: Подстрока третьего размера с отдельными символами . Итак, проблема в следующем:
You are given an integer arraynumsconsisting ofnelements, and an integerk.Find a contiguous subarray whose length is equal tokthat has the maximum average value and return this value. Any answer with a calculation error less than10-5will be accepted. Example: Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000 Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
Из вышеупомянутой задачи мы можем вывести, что нам дан числовой массив и число (k), и мы должны найти непрерывный подмассив длины (k), который имеет наибольшее среднее значение и возвращает наибольшее среднее значение. Теперь поговорим о подходах, которые можно использовать для решения этой проблемы:
1. Грубая сила | Сложность времени: O (n2)
2. Техника скользящего окна | Сложность времени: O (n)
Первый подход очень прост по своей природе, но он требует много времени, и для решения этой проблемы я хотел бы, чтобы вы все попробовали это самостоятельно, поскольку это очень просто. Мы будем обсуждать подход скользящего окна для этой проблемы.
Подход со скользящим окном: основная идея состоит в том, чтобы создать окно размера k, затем пройти это окно по массиву, добавив последний элемент и отбросив предыдущий, а затем разделив его на k, чтобы найти и сравните среднее значение, чтобы получить самый большой средний подмассив. Итак, мы создаем две переменные: Current Sum и Max Sum, и сохраняем сумму первых k элементов в текущей сумме перед установкой Max Sum равной Current Sum. Теперь мы начинаем цикл по массиву, начиная с индекса k и идя до конца, обновляя текущую сумму, добавляя более поздний элемент и удаляя предыдущий, пока мы не достигнем наибольшей суммы, соответствующей размеру окна k, и мы просто разделите его на k, чтобы получить среднее значение. Код для этого можно найти ниже.
Обзор: мы узнали о двух очень полезных алгоритмах, базовых, но очень полезных алгоритмах в этой части серии «7 основных алгоритмов, которые должен знать каждый начинающий кодировщик», которые помогут вам в решении проблем в массиве / списке тем, связанном списке, строка и в технических интервью тоже. Кроме того, это знаменует конец этой серии.
Примечание редактора: прежде всего, спасибо за то, что вы придерживались статьи до конца; пожалуйста, аплодируйте и следите за новостями, если вы узнали что-то новое.
