все Python 3Алгоритмы и структуры данныхфункция

Два указателя (two pointers)

техники

Два индекса движутся навстречу друг другу или в одном направлении. O(n) для задач на отсортированных массивах.

Синтаксис

lo, hi = 0, len(arr)-1
while lo < hi: ...

Сходящаяся пара указателей корректна только на отсортированных данных — на произвольном списке она молча вернёт неверный ответ. Сортировать самому значит заплатить O(n log n) и потерять исходные позиции, поэтому в задачах, где нужны именно индексы, обычно выигрывает словарь за один проход. И следите за границей цикла: while lo < hi не даёт сложить элемент сам с собой, а lo <= hi это разрешает.

Примеры

# Сумма двух чисел в отсортированном массиве
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr)-1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target: return (lo, hi)
        elif s < target: lo += 1
        else: hi -= 1
    return None
print(two_sum_sorted([1,2,3,4,6], 6))  # → (1, 3) (это 2+4)

# Проверка палиндрома
def is_palindrome(s):
    lo, hi = 0, len(s)-1
    while lo < hi:
        if s[lo] != s[hi]: return False
        lo += 1; hi -= 1
    return True
print(is_palindrome('racecar'))  # → True
print(is_palindrome('hello'))    # → False

# Удаление дубликатов in-place
def remove_dups(arr):
    if not arr: return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1
arr = [1,1,2,3,3,4]
k = remove_dups(arr)
print(arr[:k])  # → [1,2,3,4]

# Слияние двух отсортированных массивов
def merge_sorted(a, b):
    i = j = 0; result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: result.append(a[i]); i+=1
        else: result.append(b[j]); j+=1
    result.extend(a[i:]); result.extend(b[j:])
    return result
print(merge_sorted([1,3,5],[2,4,6]))  # → [1,2,3,4,5,6]

# Контейнер с наибольшим объёмом
def max_area(heights):
    lo, hi = 0, len(heights)-1
    best = 0
    while lo < hi:
        area = (hi-lo) * min(heights[lo],heights[hi])
        best = max(best, area)
        if heights[lo] < heights[hi]: lo+=1
        else: hi-=1
    return best
print(max_area([1,8,6,2,5,4,8,3,7]))  # → 49

См. также

Частые ошибки

Открыть в полном глоссарииdocs.python.orgСообщить о неточности