SprintCode.pro
Подготовка к алгоритмическим задачам

Two Pointers (Два указателя): Разбор техники для начинающих
Почему технику двух указателей часто используют на собеседованиях?
Техника двух указателей — это не просто алгоритмический трюк. Она показывает ваше умение:
- Оптимизировать решения
- Работать с упорядоченными данными
- Находить элегантные решения сложных задач
- Экономить память
Давайте разберем технику по шагам
Что такое два указателя?
Представьте, что у вас есть отсортированный массив чисел. Вместо того, чтобы перебирать все элементы подряд, мы используем два "указателя" (индекса), которые двигаются навстречу друг другу или в одном направлении.
Например:
const array = [1, 2, 3, 4, 5, 6]; let left = 0; // указывает на 1 let right = array.length - 1; // указывает на 6
Классическая задача: Поиск пары с заданной суммой в отсортированном массиве
Решение 1: Простой перебор (неоптимально)
function findPairSimple(array, target) { for (let i = 0; i < array.length; i++) { for (let j = i + 1; j < array.length; j++) { if (array[i] + array[j] === target) { return [i, j]; } } } return []; }
Пройди собеседование в топ-компанию
Платформа для подготовки
Решай алгоритмические задачи как профи
✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь
Начать сейчас
Решение 2: Используем два указателя (оптимально)
function findPairOptimal(array, target) { let left = 0; let right = array.length - 1; // Важно: массив должен быть отсортирован! const sortedArray = [...array].sort((a, b) => a - b); while (left < right) { const currentSum = sortedArray[left] + sortedArray[right]; if (currentSum === target) { return [left, right]; } else if (currentSum < target) { left++; // нужна большая сумма } else { right--; // нужна меньшая сумма } } return []; }
Другие задачи, где применяются два указателя
- Удаление дубликатов из отсортированного массива
function removeDuplicates(array) { if (!array.length) { return 0; } let uniquePosition = 0; for (let i = 1; i < array.length; i++) { if (array[i] !== array[uniquePosition]) { uniquePosition++; array[uniquePosition] = array[i]; } } // Обрезаем массив до уникальных элементов array.length = uniquePosition + 1; return array.length; }
- Слияние двух отсортированных массивов
function mergeSortedArrays(A, B) { const result = []; let i = 0; let j = 0; while (i < A.length && j < B.length) { if (A[i] <= B[j]) { result.push(A[i]); i++; } else { result.push(B[j]); j++; } } // Добавляем оставшиеся элементы result.push(...A.slice(i)); result.push(...B.slice(j)); return result; }
Советы по использованию техники
-
Когда применять:
- Работа с отсортированными массивами
- Поиск пар элементов
- Задачи на подсчёт или перемещение элементов
-
На что обратить внимание:
- Правильные условия остановки
- Корректное перемещение указателей
- Обработка краевых случаев
Типичные ошибки начинающих
- Забывают проверять границы массива
- Неправильно выбирают направление движения указателей
- Упускают особые случаи (пустой массив, один элемент)
Продвинутые варианты техники
- Три указателя:
// Пример: поиск трёх чисел с заданной суммой function threeSum(nums, target = 0) { const results = []; nums.sort((a, b) => a - b); for (let i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; // пропуск дубликатов let left = i + 1; let right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === target) { results.push([nums[i], nums[left], nums[right]]); while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (sum < target) { left++; } else { right--; } } } return results; }
- Быстрое и медленное указатели:
// Пример: поиск цикла в связном списке function hasCycle(head) { if (!head || !head.next) return false; let slow = head; let fast = head.next; while (fast && fast.next) { if (slow === fast) return true; slow = slow.next; fast = fast.next.next; } return false; }
Заключение
Техника двух указателей — мощный инструмент, который позволяет:
- Оптимизировать решения многих задач
- Уменьшить использование памяти
- Написать более элегантный и понятный код
Главное — научиться видеть задачи, где эта техника применима, и помнить о её ограничениях. С практикой вы начнёте замечать паттерны, где два указателя могут превратить сложную задачу в простую и эффективную.