MidПрактика13 min

Паттерн Two Pointers

Техника двух указателей для решения задач на массивах и строках

AlgoArrays and strings

Идея паттерна

Two Pointers (два указателя) — техника, при которой мы используем два индекса для обхода массива. Это часто позволяет свести решение с O(n²) до O(n).

Два основных варианта:

  1. Навстречу друг другу — left идёт вправо, right идёт влево
  2. В одном направлении — slow и fast двигаются вправо с разной скоростью
Вариант 1: Навстречу
[1, 2, 3, 4, 5, 6, 7]
 L->              <-R

Вариант 2: В одном направлении
[1, 2, 3, 4, 5, 6, 7]
 S->
    F->

Когда использовать

  • Массив отсортирован (или можно отсортировать)
  • Нужно найти пару/тройку с определённым свойством
  • Нужно разделить массив на части
  • Работа с палиндромами
  • Нужно удалить/перемещать элементы in-place

Задача 1: Two Sum (отсортированный массив)

Условие: дан отсортированный массив, найти два числа с заданной суммой.

function twoSumSorted(array $arr, int $target): array
{
    $left = 0;
    $right = count($arr) - 1;

    while ($left < $right) {
        $currentSum = $arr[$left] + $arr[$right];

        if ($currentSum === $target) {
            return [$left, $right];
        } elseif ($currentSum < $target) {
            $left++;       // Need more — move left
        } else {
            $right--;      // Need less — move right
        }
    }

    return [];
}

// Example: arr=[1,2,3,4,6], target=6
// left=0, right=4: 1+6=7 > 6 -> right=3
// left=0, right=3: 1+4=5 < 6 -> left=1
// left=1, right=3: 2+4=6 == 6 -> [1, 3]
**Сложность:** O(n) времени, O(1) памяти.

Сравни с наивным подходом O(n²):

// O(n²) — brute force all pairs
function twoSumBrute(array $arr, int $target): array
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$i] + $arr[$j] === $target) {
                return [$i, $j];
            }
        }
    }
    return [];
}
## Задача 2: Three Sum

Условие: найти все тройки чисел, дающие сумму 0.

function threeSum(array $nums): array
{
    sort($nums); // O(n log n)
    $result = [];
    $n = count($nums);

    for ($i = 0; $i < $n - 2; $i++) {
        // Skip duplicates for i
        if ($i > 0 && $nums[$i] === $nums[$i - 1]) {
            continue;
        }

        $left = $i + 1;
        $right = $n - 1;

        while ($left < $right) {
            $total = $nums[$i] + $nums[$left] + $nums[$right];

            if ($total === 0) {
                $result[] = [$nums[$i], $nums[$left], $nums[$right]];
                // Skip duplicates
                while ($left < $right && $nums[$left] === $nums[$left + 1]) {
                    $left++;
                }
                while ($left < $right && $nums[$right] === $nums[$right - 1]) {
                    $right--;
                }
                $left++;
                $right--;
            } elseif ($total < 0) {
                $left++;
            } else {
                $right--;
            }
        }
    }

    return $result;
}

// Example: [-1, 0, 1, 2, -1, -4]
// Sorted: [-4, -1, -1, 0, 1, 2]
// Result: [[-1, -1, 2], [-1, 0, 1]]
**Сложность:** O(n²) времени (сортировка + цикл с two pointers), O(1) доп. памяти.

Задача 3: Container With Most Water

Условие: массив высот, найти максимальную площадь контейнера.

Высоты:  [1, 8, 6, 2, 5, 4, 8, 3, 7]

  8 |   |               |
  7 |   |           |   |   |
  6 |   |   |       |   |   |
  5 |   |   |   |   |   |   |
  4 |   |   |   | | |   |   |
  3 |   |   |   | | | | |   |
  2 |   |   | | | | | | |   |
  1 | | |   | | | | | | |   |
    +-+-+-+-+-+-+-+-+-+-+
    0 1 2 3 4 5 6 7 8

function maxArea(array $heights): int
{
    $left = 0;
    $right = count($heights) - 1;
    $maxWater = 0;

    while ($left < $right) {
        $width = $right - $left;
        $height = min($heights[$left], $heights[$right]);
        $area = $width * $height;
        $maxWater = max($maxWater, $area);

        // Move the pointer with smaller height
        if ($heights[$left] < $heights[$right]) {
            $left++;
        } else {
            $right--;
        }
    }

    return $maxWater;
}

// Why move the smaller one?
// If we move the taller one — width decreases and height won't increase
// (limited by the shorter one). Area will definitely decrease.
// Moving the shorter one — there's a chance to find a taller wall.
**Сложность:** O(n) времени, O(1) памяти.

Задача 4: Проверка палиндрома

function isPalindrome(string $s): bool
{
    // Keep only letters and digits, convert to lowercase
    $s = preg_replace('/[^a-zA-Z0-9]/', '', strtolower($s));

    $left = 0;
    $right = strlen($s) - 1;
    while ($left < $right) {
        if ($s[$left] !== $s[$right]) {
            return false;
        }
        $left++;
        $right--;
    }

    return true;
}

// "A man, a plan, a canal: Panama" -> true
// "racecar" -> true
// "hello" -> false
## Задача 5: Удаление элемента in-place (slow/fast) 
// Remove all occurrences of $val from array
function removeElement(array &$arr, int $val): int
{
    $slow = 0;
    for ($fast = 0; $fast < count($arr); $fast++) {
        if ($arr[$fast] !== $val) {
            $arr[$slow] = $arr[$fast];
            $slow++;
        }
    }
    return $slow; // New length
}

// arr = [3, 2, 2, 3], val = 3
// fast=0: arr[0]=3, skip
// fast=1: arr[1]=2, arr[0]=2, slow=1
// fast=2: arr[2]=2, arr[1]=2, slow=2
// fast=3: arr[3]=3, skip
// Result: [2, 2, ...], length = 2
Визуализация slow/fast: 
Начало:  [3, 2, 2, 3],  val=3
          S
          F

Шаг 1:   [3, 2, 2, 3]   arr[F]=3, пропускаем
          S
             F

Шаг 2:   [2, 2, 2, 3]   arr[F]=2 != 3, копируем
             S
                F

Шаг 3:   [2, 2, 2, 3]   arr[F]=2 != 3, копируем
                S
                   F

Шаг 4:   [2, 2, 2, 3]   arr[F]=3, пропускаем
                S

Результат: [2, 2, ...]  slow = 2

Задача 6: Сортировка цветов (Dutch National Flag)

// Array of 0, 1, 2. Sort in-place in a single pass.
function sortColors(array &$nums): void
{
    $low = 0;                       // Boundary for 0
    $mid = 0;                       // Current element
    $high = count($nums) - 1;      // Boundary for 2

    while ($mid <= $high) {
        if ($nums[$mid] === 0) {
            [$nums[$low], $nums[$mid]] = [$nums[$mid], $nums[$low]];
            $low++;
            $mid++;
        } elseif ($nums[$mid] === 1) {
            $mid++;
        } else { // nums[mid] === 2
            [$nums[$mid], $nums[$high]] = [$nums[$high], $nums[$mid]];
            $high--;
            // Don't increment mid — need to check the new element
        }
    }
}
// [2, 0, 2, 1, 1, 0] -> [0, 0, 1, 1, 2, 2]
## Задача 7: Сжатие массива (remove duplicates) 
// Remove duplicates from sorted array
function removeDuplicates(array &$nums): int
{
    if (empty($nums)) {
        return 0;
    }

    $slow = 0;
    for ($fast = 1; $fast < count($nums); $fast++) {
        if ($nums[$fast] !== $nums[$slow]) {
            $slow++;
            $nums[$slow] = $nums[$fast];
        }
    }

    return $slow + 1;
}
// [1, 1, 2, 2, 3] -> [1, 2, 3, ...], returns 3
## Шаблон для решения задач с Two Pointers 
// Template 1: Moving towards each other
function twoPointersOpposite(array $arr): mixed
{
    $left = 0;
    $right = count($arr) - 1;

    while ($left < $right) {
        // Compute something with $arr[$left] and $arr[$right]

        if ($conditionToMoveLeft) {
            $left++;
        } elseif ($conditionToMoveRight) {
            $right--;
        } else {
            // Found answer or process
            $left++;
            $right--;
        }
    }
}

// Template 2: Same direction (slow/fast)
function twoPointersSameDirection(array &$arr): int
{
    $slow = 0;

    for ($fast = 0; $fast < count($arr); $fast++) {
        if (someCondition($arr[$fast])) {
            $arr[$slow] = $arr[$fast];
            $slow++;
        }
    }

    return $slow; // Boundary of processed part
}
> **Запомни:** Two Pointers работает когда: 1) Массив отсортирован — используй встречные указатели. 2) Нужно фильтрация/перемещение in-place — используй slow/fast. 3) Ключевой инсайт — на каждом шаге один из указателей двигается, значит максимум O(n) шагов.

Итоги

Задача Подход Сложность
Two Sum (sorted) Навстречу O(n)
Three Sum Фикс + навстречу O(n²)
Container With Water Навстречу O(n)
Палиндром Навстречу O(n)
Remove Element Slow/Fast O(n)
Sort Colors 3 указателя O(n)
Remove Duplicates Slow/Fast O(n)

Проверь себя

В задаче Two Sum на отсортированном массиве [1, 2, 4, 6, 10], target=8. Какие шаги выполнят указатели?

Какова временная сложность алгоритма Three Sum?

В задаче Sort Colors (Dutch National Flag) почему при swap с high мы НЕ увеличиваем mid? ```php if ($nums[$mid] === 2) { swap($nums[$mid], $nums[$high]); $high--; // mid НЕ увеличивается! } ```

Какой вариант Two Pointers используется для удаления элементов in-place?

Code Challenges

Переворот строки на месте

Переверните строку на месте, используя технику двух указателей. Верните перевёрнутую строку.

Test Cases

1. Input: hello→ Expected: olleh
2. Input: abcdef→ Expected: fedcba
3. Input: a→ Expected: a

Связанные темы

Паттерн Sliding Window

Связанная тема

Prefix Sum

Связанная тема