Метод двух указателей (Two Pointers) в алгоритмике — это техника для эффективной работы с массивами, особенно отсортированными, где два указателя (индекса) двигаются навстречу друг другу или в одном направлении для поиска пар, сумм, или решения задач за (O(N)) времени вместо (O(N^{2}))

Это реализуется в PHP как обычное итерирование с двумя переменными-индексами в цикле while или for для сравнения и перемещения указателей. 

Как это работает: 

• Инициализация: Создаются два указателя, left (левый) и right (правый), указывающие в начало и конец массива соответственно (не обязательно на конец, могут и оба на начало, и оба на конец).
• Условие: Цикл продолжается, пока left < right (или другое условие остановки).
• Действие: Внутри цикла сравниваются элементы, на которые указывают left и right, и в зависимости от результата один из указателей сдвигается.
• Сдвиг:

1. Если нужен меньший элемент, left++.
2. Если нужен больший, right–.
3. Если найдена пара/решение, можно сдвинуть оба или завершить. 

Пример задачи (Поиск пары в отсортированном массиве, дающей заданную сумму):

function findPairWithSum(array $arr, int $targetSum): ?array {
    $left = 0;
    $right = count($arr) - 1;

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

        if ($currentSum === $targetSum) {
            // Нашли пару!
            return [$arr[$left], $arr[$right]];
        } elseif ($currentSum < $targetSum) {
            // Сумма меньше, нужно увеличить, двигаем левый указатель вправо
            $left++;
        } else {
            // Сумма больше, нужно уменьшить, двигаем правый указатель влево
            $right--;
        }
    }
    // Пара не найдена
    return null;
}

$sortedArray = [2, 7, 11, 15, 20];
$target = 22;
$result = findPairWithSum($sortedArray, $target);
if ($result) {
    echo "Найденная пара: " . $result[0] . ", " . $result[1] . "\n"; // Вывод: 2, 20
} else {
    echo "Пара не найдена\n";
}

А вот прям антипример – без двух указателей. Двойной цикл, перебираем все пары. Это уже O(n^2), как раз то, от чего two pointers спасают.

function findPairWithSumBruteforce(array $arr, int $targetSum): ?array {
    $n = count($arr);

    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$i] + $arr[$j] === $targetSum) {
                return [$arr[$i], $arr[$j]];
            }
        }
    }

    return null;
}

$sortedArray = [2, 7, 11, 15, 20];
$target = 22;

$result = findPairWithSumBruteforce($sortedArray, $target);

if ($result) {
    echo "Найденная пара: " . $result[0] . ", " . $result[1] . "\n";
} else {
    echo "Пара не найдена\n";
}

Пример задачи (слить два отсортированных массива в один отсортированный)

Неправильный вариант с 2-мя циклами.

<?php

function mergeTwoSortedArraysNoPointersQuadratic(array $arr1, array $arr2): array {
    $result = array_merge($arr1, $arr2);

    $n = count($result);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($result[$j] < $result[$i]) {
                $tmp = $result[$i];
                $result[$i] = $result[$j];
                $result[$j] = $tmp;
            }
        }
    }

    return $result;
}

// Пример:
$array1 = [1, 3, 5, 7];
$array2 = [2, 4, 6, 8, 10];

print_r(mergeTwoSortedArraysNoPointersQuadratic($array1, $array2));

Правильный вариант с методом двух указателей.

<?php

function mergeTwoSortedArrays($arr1, $arr2) {
    $merged = []; // Новый массив для результата
    $i = 0; // Указатель для $arr1
    $j = 0; // Указатель для $arr2

    // Пока оба указателя в пределах своих массивов
    while ($i < count($arr1) && $j < count($arr2)) {
        if ($arr1[$i] <= $arr2[$j]) {
            $merged[] = $arr1[$i];
            $i++;
        } else {
            $merged[] = $arr2[$j];
            $j++;
        }
    }

    // Добавляем оставшиеся элементы из $arr1 (если есть)
    while ($i < count($arr1)) {
        $merged[] = $arr1[$i];
        $i++;
    }

    // Добавляем оставшиеся элементы из $arr2 (если есть)
    while ($j < count($arr2)) {
        $merged[] = $arr2[$j];
        $j++;
    }

    return $merged;
}

// Пример использования:
$array1 = [1, 3, 5, 7];
$array2 = [2, 4, 6, 8, 10];

$result = mergeTwoSortedArrays($array1, $array2);
print_r($result);
// Вывод: Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 [8] => 10 )

$array3 = [10, 20, 30];
$array4 = [5, 15];
$result2 = mergeTwoSortedArrays($array3, $array4);
print_r($result2);
// Вывод: Array ( [0] => 5 [1] => 10 [2] => 15 [3] => 20 [4] => 30 )

?>

Или можно так, “for-стайл”, и чтобы указатели i и j объявлялись прямо в for. Я еще убрал лишние count() внутри циклов (их лучше один раз посчитать, чтобы не дергать постоянно).

<?php

function mergeTwoSortedArrays(array $arr1, array $arr2): array {
    $merged = [];
    $n1 = count($arr1);
    $n2 = count($arr2);

    // i и j объявлены внутри for
    for ($i = 0, $j = 0; $i < $n1 && $j < $n2; ) {
        if ($arr1[$i] <= $arr2[$j]) {
            $merged[] = $arr1[$i];
            $i++;
        } else {
            $merged[] = $arr2[$j];
            $j++;
        }
    }

    // добиваем хвост arr1
    for (; $i < $n1; $i++) {
        $merged[] = $arr1[$i];
    }

    // добиваем хвост arr2
    for (; $j < $n2; $j++) {
        $merged[] = $arr2[$j];
    }

    return $merged;
}

// Пример:
$array1 = [1, 3, 5, 7];
$array2 = [2, 4, 6, 8, 10];
print_r(mergeTwoSortedArrays($array1, $array2));

$array3 = [10, 20, 30];
$array4 = [5, 15];
print_r(mergeTwoSortedArrays($array3, $array4));