Два указателя: от противоположных концов
Используйте левый и правый указатели, движущиеся навстречу друг другу, чтобы решать задачи о сумме пары в отсортированных массивах, корректных палиндромах и удержании дождевой воды
«Два указателя: от противоположных концов» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Идея двух указателей
Техника двух указателей использует две переменные-индекса, которые движутся навстречу друг другу (или в одном направлении), чтобы уменьшить потребность во вложенных циклах. Вместо проверки каждой пары за O(n²) вы продвигаетесь при каждом сравнении и завершаете работу за O(n). Почти всегда сначала требуется отсортировать массив, поскольку сортировка позволяет определить направление перемещения каждого указателя по тому, слишком велика или слишком мала текущая сумма пары.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []Два слагаемых в отсортированном массиве
В отсортированном массиве установите один указатель на левом конце (наименьшее значение), а другой — на правом (наибольшее значение). Если сумма слишком мала, переместите левый указатель вправо, чтобы увеличить её. Если сумма слишком велика, переместите правый указатель влево, чтобы уменьшить её. На каждой итерации продвигается хотя бы один указатель, поэтому цикл выполняется не более n раз: общая сложность после сортировки — O(n). Важно, что правильность каждого перемещения доказуема благодаря отсортированному порядку.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Проверка на палиндром
Строка является палиндромом, если читается одинаково слева направо и справа налево. Установите два указателя на обоих концах и двигайте их к центру: сравнивайте символы, пропускайте небуквенно-цифровые символы и остановитесь, когда указатели пересекутся. Алгоритм работает за O(n) времени и использует O(1) дополнительной памяти — это значительно эффективнее, чем разворачивать строку и сравнивать её с исходной, выделяя O(n) дополнительной памяти.
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseТри слагаемых: сортировка и два указателя
Задача о трёх слагаемых требует найти все уникальные тройки с суммой, равной нулю. Отсортируйте массив, зафиксируйте каждый элемент nums[i], а затем выполните поиск двумя указателями в оставшемся подмассиве для пары с суммой -nums[i]. Пропускайте повторы как зафиксированного элемента, так и найденной пары, чтобы избежать повторяющихся троек. Общее время: O(n²) после сортировки за O(n log n).
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Контейнер с максимальным количеством воды
Для заданных высот вертикальных линий найдите две линии, образующие контейнер с наибольшим количеством воды. Площадь равна min(height[left], height[right]) × (right - left). Жадно перемещайте внутрь указатель, расположенный у более короткой линии: перемещение указателя у более высокой линии только уменьшит ширину, не увеличив ограничивающую высоту. Этот жадный выбор доказуемо оптимален и даёт время O(n).
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Возведение в квадрат отсортированного массива
Возведите в квадрат каждый элемент отсортированного массива, который может содержать отрицательные числа, и верните результат в отсортированном порядке. Квадраты отрицательных чисел имеют большие значения, а квадраты положительных чисел в центре массива — малые. Установите два указателя на обоих концах и заполняйте результирующий массив справа налево, от наибольшего значения к наименьшему. Время O(n) и O(n) памяти под результат — значительно лучше, чем сначала возводить числа в квадрат, а затем сортировать их за O(n log n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Задача о захвате дождевой воды
Количество воды, удерживаемой в индексе i, равно min(max_left, max_right) - height[i]. Подход с двумя указателями поддерживает текущие значения max_left и max_right. Когда max_left < max_right, ограничивающей является левая сторона — обрабатывайте левый указатель. В противном случае обрабатывайте правый. Это устраняет необходимость в отдельных массивах максимумов слева и справа и обеспечивает O(1) дополнительной памяти.
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Почему жадное перемещение указателя работает
На собеседовании часто задают дополнительный вопрос: почему безопасно отбросить указатель с меньшим значением? Краткое доказательство для задачи о контейнере с максимальным количеством воды: предположим, что height[left] < height[right]. Любая пара (left, j) при j < right имеет площадь ≤ height[left] × (j-left) < height[left] × (right-left) ≤ текущей площади. Поэтому ни одна пара, начинающаяся в left и имеющая правый индекс меньше right, не может превзойти текущую площадь. Мы безопасно пропускаем их, продвигая left.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Пара с минимальной разностью в отсортированном массиве
Найдите пару чисел в отсортированном массиве с наименьшей абсолютной разностью. Используйте два соседних указателя, а не указатели на противоположных концах, и перемещайте их вместе: |nums[i] - nums[i+1]| для всех последовательных пар. В отсортированном массиве минимальная разность всегда находится между соседними элементами, поскольку сортировка объединяет близкие значения. После сортировки это выполняется за O(n).
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Шаблон для двух указателей с противоположных концов
Большинство задач с двумя указателями, движущимися от противоположных концов, следуют одной и той же структуре. Освоив этот шаблон, Вы сможете быстро адаптировать его в условиях нехватки времени. Ключевые решения таковы: (1) какое условие перемещает левый указатель, (2) какое условие перемещает правый указатель, (3) что считается решением и (4) как обрабатывать дубликаты. Перед написанием кода потренируйтесь извлекать эти решения из условия задачи.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultПодсчёт допустимых пар с помощью двух указателей
Два указателя также позволяют эффективно подсчитывать пары. Для задачи «подсчитать пары с суммой < заданного значения» в отсортированном массиве зафиксируйте левый указатель и с помощью правого найдите крайний справа допустимый индекс. Все пары от текущего левого элемента до найденного правого допустимы — добавьте right - left к счётчику и переместите левый указатель. Так Вы подсчитаете все допустимые пары за O(n), а не за O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Быстрая проверка
Проверьте, насколько хорошо Вы поняли концепции структур данных и алгоритмов — подготовки к собеседованиям по программированию, рассмотренные в этом уроке.
Итоги урока
В этом уроке Вы узнали, что два указателя с противоположных концов заменяют перечисление пар за O(n²) схождением слева направо за O(n) в отсортированных массивах, решение о том, какой указатель перемещать, следует из монотонного свойства задачи: нужно двигать сторону, которая в данный момент ограничивает продвижение, а задачи о трёх суммах, контейнере с наибольшим количеством воды, захвате дождевой воды и проверке палиндрома сводятся к одному и тому же базовому шаблону. Далее мы рассмотрим шаблоны с медленным и быстрым указателями.
Часто задаваемые вопросы
Урок «Два указателя: от противоположных концов» бесплатный?
Да — полный текст урока «Два указателя: от противоположных концов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Два указателя: от противоположных концов»?
Используйте левый и правый указатели, движущиеся навстречу друг другу, чтобы решать задачи о сумме пары в отсортированных массивах, корректных палиндромах и удержании дождевой воды Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Два указателя: от противоположных концов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Основы массивов и операции на месте
- Префиксные суммы и текущие итоги
- Два указателя: от противоположных концов
- Два указателя: медленный и быстрый