Два указателя

Два указателя (two pointers) — приём, где два индекса двигаются по массиву навстречу друг другу или в одном направлении, вместо вложенных циклов. Часто превращает O(n²)-решение в O(n).

Классическая задача: «найти два числа в отсортированном массиве, сумма которых равна цели»:

int[] twoSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) left++;    // сумма мала — двигаем левый указатель вправо
        else right--;                  // сумма велика — двигаем правый указатель влево
    }
    return new int[]{-1, -1};
}

Копнуть глубже

Когда применять. Признак, что стоит подумать про два указателя: задача про отсортированный массив/строку, и нужно найти пару/тройку элементов с каким-то условием на сумму, разность, или просто пройтись с двух концов (например, проверить палиндром).

Почему это быстрее. Наивное решение перебирает все пары — O(n²). Два указателя используют тот факт, что массив отсортирован: если текущая сумма меньше нужной, точно нет смысла уменьшать правый указатель (станет ещё меньше) — нужно увеличивать левый. Это отбрасывает огромные куски перебора, не теряя правильности, и сводит решение к одному проходу — O(n).

🎤 Закрыл тему, если можешь объяснить:

• идею двух указателей на примере two sum в отсортированном массиве;
• по каким признакам задачи понять, что подходит этот приём (если дошёл до 2-го слоя).