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 [];
}

Другие задачи, где применяются два указателя

1. Удаление дубликатов из отсортированного массива

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;
}

1. Слияние двух отсортированных массивов

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;
}

Советы по использованию техники

1. Когда применять:

   • Работа с отсортированными массивами
   • Поиск пар элементов
   • Задачи на подсчёт или перемещение элементов

2. На что обратить внимание:

   • Правильные условия остановки
   • Корректное перемещение указателей
   • Обработка краевых случаев

Типичные ошибки начинающих

1. Забывают проверять границы массива
2. Неправильно выбирают направление движения указателей
3. Упускают особые случаи (пустой массив, один элемент)

Продвинутые варианты техники

1. Три указателя:

// Пример: поиск трёх чисел с заданной суммой
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;
}

1. Быстрое и медленное указатели:

// Пример: поиск цикла в связном списке
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;
}

Заключение

Техника двух указателей — мощный инструмент, который позволяет:

• Оптимизировать решения многих задач
• Уменьшить использование памяти
• Написать более элегантный и понятный код

Главное — научиться видеть задачи, где эта техника применима, и помнить о её ограничениях. С практикой вы начнёте замечать паттерны, где два указателя могут превратить сложную задачу в простую и эффективную.