Two Pointers

Один из самых элегантных паттернов для работы с массивами и строками: два указателя движутся навстречу или в одном направлении, сокращая сложность с O(n²) до O(n)

#1. Суть паттерна

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

#1.1 Термины

Алгоритм — точная последовательность шагов для решения задачи.

Структура данных — способ организации и хранения данных для эффективного доступа и изменения.

Массив — упорядоченная коллекция элементов одного типа.

Подмассив — непрерывная часть массива (элементы идут подряд).

Подпоследовательность — элементы массива в том же порядке, но не обязательно непрерывные.

Подстрока — непрерывная часть строки.

Префикс — начало строки (подстрока, начинающаяся с первого символа).

Суффикс — конец строки (подстрока, заканчивающаяся последним символом).

Временная сложность — оценка времени выполнения алгоритма в зависимости от размера входных данных.

Пространственная сложность — оценка объёма памяти, используемого алгоритмом.

O-нотация (Big O) — способ описания верхней границы сложности алгоритма.

Хэш-функция — функция, преобразующая входные данные в число (хэш).

Хэш-таблица — структура данных для быстрого поиска по ключу (в среднем O(1)).

Коллизия — ситуация, когда два разных ключа дают одинаковый хэш.

#Когда применять

✅ Отсортированный массив — поиск пары с заданной суммой
✅ Палиндромы — проверка симметрии строки/массива
✅ Слияние — объединение двух отсортированных массивов
✅ Удаление дубликатов — in-place модификация
✅ Разделение — partition по условию (как в Quick Sort)

#Типы движения указателей

Тип	Описание	Пример
Навстречу	`left` от начала, `right` от конца, движутся к центру	Two Sum в отсортированном массиве
В одном направлении	Оба движутся слева направо, `fast` опережает `slow`	Удаление дубликатов
Разные скорости	`slow` += 1, `fast` += 2	Поиск середины (Floyd's Algorithm)

#2. Базовый шаблон: навстречу друг другу

def two_pointers_opposite(arr, target):
    left, right = 0, len(arr) - 1

    while left < right:
        current = arr[left] + arr[right]

        if current == target:
            return [left, right]
        elif current < target:
            left += 1      # Нужно больше
        else:
            right -= 1     # Нужно меньше

    return [-1, -1]

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

Инициализируем left = 0, right = n - 1
Вычисляем текущее значение (сумму, произведение и т.д.)
Если равно цели — нашли ответ
Если меньше цели — увеличиваем left (движемся к большим значениям)
Если больше цели — уменьшаем right (движемся к меньшим значениям)

Почему это работает? В отсортированном массиве движение left вправо увеличивает сумму, движение right влево — уменьшает.

#3. Шаблон: в одном направлении (Fast & Slow)

def two_pointers_same_direction(arr):
    slow = 0

    for fast in range(len(arr)):
        # Условие для продвижения slow
        if some_condition(arr[fast]):
            arr[slow] = arr[fast]
            slow += 1

    return slow  # Новая длина

#Пример: удаление дубликатов

def remove_duplicates(nums):
    """Удалить дубликаты из отсортированного массива in-place"""
    if not nums:
        return 0

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1  # Новая длина

#4. Разбор задач

#Задача 1: Two Sum II — Input Array Is Sorted (LeetCode 167) 🟦 Easy

Ссылка: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Условие: Дан отсортированный по неубыванию массив целых чисел numbers и целевое значение target. Необходимо найти два числа в массиве, сумма которых равна target. Верните индексы этих чисел (в 1-based формате, т.е. первый индекс = 1, второй индекс = 2).

Гарантируется, что решение существует и каждый элемент можно использовать только один раз.

Примеры:

Ввод: numbers = [2, 7, 11, 15], target = 9 Вывод: [1, 2] Объяснение: numbers[0] + numbers[1] = 2 + 7 = 9, возвращаем [1, 2] (1-based индексы)

Ввод: numbers = [2, 3, 4], target = 6 Вывод: [1, 3]

Ввод: numbers = [-1, 0], target = -1 Вывод: [1, 2]

Ограничения:

2 <= numbers.length <= 3 × 10⁴
-1000 <= numbers[i] <= 1000
numbers отсортирован по неубыванию
-1000 <= target <= 1000
Существует ровно одно решение

💡 Подсказка: Поскольку массив отсортирован, можно использовать два указателя: один в начале, другой в конце. Если сумма меньше target — двигаем левый указатель вправо (увеличиваем сумму), если больше — двигаем правый влево (уменьшаем сумму).

#Визуализация

Массив: [2, 7, 11, 15], target = 9

Шаг 1:                    Шаг 2:
┌───┬───┬───┬───┐         ┌───┬───┬───┬───┐
│ 2 │ 7 │ 11│ 15│         │ 2 │ 7 │ 11│ 15│
└───┴───┴───┴───┘         └───┴───┴───┴───┘
 ↑               ↑         ↑           ↑
left=0          right=3   left=0      right=2
sum = 17 > 9 →              sum = 13 > 9 →
right--                     right--

Шаг 3:                    Шаг 4 (НАЙДЕНО):
┌───┬───┬───┬───┐         ┌───┬───┬───┬───┐
│ 2 │ 7 │ 11│ 15│         │ 2 │ 7 │ 11│ 15│
└───┴───┴───┴───┘         └───┴───┴───┴───┘
 ↑       ↑                 ↑   ↑
left=0  right=1           left=0  right=1
sum = 9 == 9 ✓            return [1, 2] (1-based)

Решение:

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]  # 1-based индексы
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return [-1, -1]

Объяснение:

Начинаем с краёв массива
Если сумма меньше target — двигаем left вправо (увеличиваем сумму)
Если сумма больше target — двигаем right влево (уменьшаем сумму)
Гарантированно найдём решение за O(n)

Сложность:

Время: O(n) — один проход
Память: O(1) — два указателя

#Задача 2: Valid Palindrome (LeetCode 125) 🟩 Easy

Ссылка: https://leetcode.com/problems/valid-palindrome/

Условие: Дана строка s. Проверить, является ли она палиндромом, учитывая только буквенно-цифровые символы (буквы и цифры) и игнорируя регистр символов.

Палиндром — это строка, которая читается одинаково слева направо и справа налево.

Примеры:

Ввод: s = "A man, a plan, a canal: Panama" Вывод: true Объяснение: "amanaplanacanalpanama" является палиндромом

Ввод: s = "race a car" Вывод: false Объяснение: "raceacar" не является палиндромом

Ввод: s = " " Вывод: true Объяснение: После удаления неалфавитных символов остаётся пустая строка, которая считается палиндромом

Ограничения:

1 <= s.length <= 10⁵
s состоит из печатных ASCII-символов

💡 Подсказка: Используйте два указателя: один в начале строки, другой в конце. Пропускайте неалфавитные символы и сравнивайте символы в нижнем регистре. Если все совпадут — это палиндром.

Решение:

def isPalindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        # Пропускаем неалфавитные символы слева
        while left < right and not s[left].isalnum():
            left += 1
        # Пропускаем неалфавитные символы справа
        while left < right and not s[right].isalnum():
            right -= 1

        # Сравниваем символы (игнорируя регистр)
        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

Объяснение:

Два указателя движутся навстречу
Пропускаем пробелы, знаки препинания
Сравниваем символы в нижнем регистре
Если все совпали — палиндром

Сложность:

Время: O(n)
Память: O(1)

#Задача 3: Container With Most Water (LeetCode 11) 🟩 Medium

Ссылка: https://leetcode.com/problems/container-with-most-water/

Условие: Дан массив целых чисел height длины n, где каждый элемент представляет высоту вертикальной линии на координате i (т.е. линия проходит от (i, 0) до (i, height[i])).

Найдите две линии, которые вместе с осью x образуют контейнер, вмещающий максимальное количество воды.

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

Примеры:

Ввод: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Вывод: 49 Объяснение: Максимальная площадь достигается между линиями на индексах 1 и 8: ширина = 7, высота = min(8, 7) = 7, площадь = 7 × 7 = 49

Ввод: height = [1, 1] Вывод: 1

Ограничения:

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

💡 Подсказка: Начните с двух указателей на краях массива (максимальная ширина). Площадь = ширина × min(высота1, высота2). Двигайте указатель с меньшей высотой — только так можно потенциально увеличить площадь.

#Визуализация

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Шаг 1 (максимальная ширина):
  8 │               │
  7 │               │                   │
  6 │       │       │
  5 │       │   │   │   │
  4 │       │   │   │   │   │
  3 │       │   │   │   │   │   │   │
  2 │       │   │   │   │   │   │   │   │
  1 │   │   │   │   │   │   │   │   │   │
    └───┴───┴───┴───┴───┴───┴───┴───┴───┘
    ↑                                   ↑
  left=0                              right=8
  width = 8, h = min(1,7) = 1
  area = 8 × 1 = 8

Шаг 2 (двинули left, т.к. height[left] < height[right]):
  8 │               │
  7 │               │                   │
  6 │       │       │
  5 │       │   │   │   │
  4 │       │   │   │   │   │
  3 │       │   │   │   │   │   │   │
  2 │       │   │   │   │   │   │   │   │
  1 │   │   │   │   │   │   │   │   │   │
    └───┴───┴───┴───┴───┴───┴───┴───┴───┘
        ↑                               ↑
      left=1                          right=8
  width = 7, h = min(8,7) = 7
  area = 7 × 7 = 49 ← МАКСИМУМ!

Решение:

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        # Площадь = ширина × минимальная высота
        width = right - left
        h = min(height[left], height[right])
        area = width * h

        max_area = max(max_area, area)

        # Двигаем указатель с меньшей высотой
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

Объяснение:

Начинаем с максимальной ширины
Площадь ограничена меньшей из двух высот
Двигаем указатель с меньшей высотой — только так можно потенциально увеличить площадь
Если двигать указатель с большей высотой, ширина уменьшится, а высота останется ≤ текущей меньшей

Почему это жадный алгоритм работает?

Мы исследуем все потенциально оптимальные конфигурации
Отбрасываем заведомо проигрышные варианты

Сложность:

Время: O(n)
Память: O(1)

#Задача 4: 3Sum (LeetCode 15) 🟩 Medium

Ссылка: https://leetcode.com/problems/3sum/

Условие: Дан массив целых чисел nums длины n. Найдите все уникальные тройки [nums[i], nums[j], nums[k]], такие что:

i, j, k различны
nums[i] + nums[j] + nums[k] == 0

Верните массив всех уникальных троек. Решение не должно содержать дублирующихся троек.

Примеры:

Ввод: nums = [-1, 0, 1, 2, -1, -4] Вывод: [[-1, -1, 2], [-1, 0, 1]] Объяснение:

nums[0] + nums[1] + nums[2] = -1 + 0 + 1 = 0
nums[0] + nums[3] + nums[4] = -1 + 2 + -1 = 0 Уникальные тройки: [-1, -1, 2] и [-1, 0, 1]

Ввод: nums = [0, 1, 1] Вывод: []

Ввод: nums = [0, 0, 0] Вывод: [[0, 0, 0]]

Ограничения:

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

💡 Подсказка: Отсортируйте массив. Зафиксируйте первый элемент, затем используйте два указателя для поиска пары с суммой, равной -nums[i]. Пропускайте дубликаты на всех уровнях.

Решение:

def threeSum(nums):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Пропускаем дубликаты для первого числа
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # Two Pointers для оставшихся двух чисел
        left, right = i + 1, n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if current_sum == 0:
                result.append([nums[i], nums[left], nums[right]])

                # Пропускаем дубликаты
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1
            elif current_sum < 0:
                left += 1
            else:
                right -= 1

    return result

Объяснение:

Сортируем массив — O(n log n)
Фиксируем первое число nums[i]
Для оставшихся используем Two Pointers для поиска пары с суммой -nums[i]
Пропускаем дубликаты на всех уровнях

Сложность:

Время: O(n²) — внешний цикл O(n) × Two Pointers O(n)
Память: O(1) — не считая результата

#Задача 5: Remove Duplicates from Sorted Array (LeetCode 26) 🟩 Easy

Ссылка: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Условие: Дан отсортированный по неубыванию массив целых чисел nums. Удалите дубликаты элементов in-place так, чтобы каждый уникальный элемент встречался только один раз. Относительный порядок элементов должен быть сохранён.

Верните новую длину массива после удаления дубликатов.

Примеры:

Ввод: nums = [1, 1, 2] Вывод: 2, nums = [1, 2, _] Объяснение: Первые два элемента равны 1 и 2 соответственно. Остальные элементы могут быть любыми.

Ввод: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] Вывод: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Ограничения:

1 <= nums.length <= 3 × 10⁴
-100 <= nums[i] <= 100
nums отсортирован по неубыванию

💡 Подсказка: Используйте два указателя: slow указывает на последний уникальный элемент, fast сканирует массив. Когда находим новый уникальный элемент — копируем его на позицию slow + 1.

Решение:

def removeDuplicates(nums):
    if not nums:
        return 0

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1

Объяснение:

slow указывает на последний уникальный элемент
fast сканирует массив
Когда находим новый уникальный элемент — копируем его на позицию slow + 1

Визуализация:

[1, 1, 2, 2, 3]
 ↑        ↑
slow     fast

[1, 2, 2, 2, 3]
    ↑     ↑
   slow  fast

[1, 2, 3, 2, 3]
       ↑        ↑
      slow     fast

Сложность:

Время: O(n)
Память: O(1)

#Задача 6: Merge Sorted Array (LeetCode 88) 🟩 Easy

Ссылка: https://leetcode.com/problems/merge-sorted-array/

Условие: Даны два отсортированных по неубыванию массива целых чисел nums1 и nums2 длины m и n соответственно.

Слейте nums2 в nums1 так, чтобы nums1 содержал все элементы в отсортированном порядке.

Массив nums1 имеет длину m + n, где первые m элементов содержат значения для слияния, а последние n элементов равны 0 и должны быть проигнорированы.

Примеры:

Ввод: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3 Вывод: [1, 2, 2, 3, 5, 6] Объяснение: Массивы [1, 2, 3] и [2, 5, 6] слиты в [1, 2, 2, 3, 5, 6]

Ввод: nums1 = [1], m = 1, nums2 = [], n = 0 Вывод: [1]

Ограничения:

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10⁹ <= nums1[i], nums2[i] <= 10⁹

💡 Подсказка: Записывайте элементы с конца массива nums1, чтобы не затереть ещё не обработанные элементы. Сравнивайте текущие элементы обоих массивов и записывайте больший.

Решение:

def merge(nums1, m, nums2, n):
    # Три указателя: с конца обоих массивов и позиции записи
    i, j, k = m - 1, n - 1, m + n - 1

    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1

Объяснение:

Записываем с конца, чтобы не затереть элементы nums1
Сравниваем текущие элементы, записываем больший
Продолжаем, пока не обработаем все элементы nums2

Почему с конца? Если записывать с начала, придётся сдвигать элементы nums1, что даст O(n²).

Сложность:

Время: O(m + n)
Память: O(1)

#Задача 7: Move Zeroes (LeetCode 283) 🟩 Easy

Ссылка: https://leetcode.com/problems/move-zeroes/

Условие: Дан массив целых чисел nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов.

Выполните операцию in-place без создания копии массива.

Примеры:

Ввод: nums = [0, 1, 0, 3, 12] Вывод: [1, 3, 12, 0, 0]

Ввод: nums = [0] Вывод: [0]

Ограничения:

1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

💡 Подсказка: Используйте два указателя: slow указывает на позицию для следующего ненулевого элемента, fast сканирует массив. Все ненулевые элементы «сжимаются» в начало.

Решение:

def moveZeroes(nums):
    slow = 0
    
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Или оптимизированная версия (меньше обменов):

def moveZeroes(nums):
    slow = 0
    
    # Сначала перемещаем все ненулевые элементы вперёд
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
    
    # Заполняем остаток нулями
    for i in range(slow, len(nums)):
        nums[i] = 0

Объяснение:

slow указывает на позицию для следующего ненулевого элемента
fast сканирует массив
Все ненулевые элементы «сжимаются» в начало

Сложность:

Время: O(n)
Память: O(1)

#Задача 8: Sort Colors (LeetCode 75) 🟩 Medium

Ссылка: https://leetcode.com/problems/sort-colors/

Условие: Дан массив nums из n объектов, окрашенных в красный, белый или синий цвет. Отсортируйте их in-place так, чтобы объекты одного цвета были рядом, а цвета шли в порядке: красный (0), белый (1), синий (2).

Используйте только константную дополнительную память.

Примеры:

Ввод: nums = [2, 0, 2, 1, 1, 0] Вывод: [0, 0, 1, 1, 2, 2]

Ввод: nums = [2, 0, 1] Вывод: [0, 1, 2]

Ограничения:

n == nums.length
1 <= n <= 300
nums[i] равно 0, 1 или 2

💡 Подсказка: Используйте три указателя (Dutch National Flag): left для 0, right для 2, current для сканирования. 0 меняем с left, 2 с right, 1 оставляем.

Решение (Dutch National Flag):

def sortColors(nums):
    left, right = 0, len(nums) - 1
    current = 0
    
    while current <= right:
        if nums[current] == 0:
            nums[left], nums[current] = nums[current], nums[left]
            left += 1
            current += 1
        elif nums[current] == 2:
            nums[right], nums[current] = nums[current], nums[right]
            right -= 1
            # current не увеличиваем — нужно проверить swapped элемент
        else:  # nums[current] == 1
            current += 1

Объяснение:

Три указателя: left для 0, right для 2, current для сканирования
0 меняем с left, 2 с right, 1 оставляем
Элементы слева от left — все 0, справа от right — все 2

Сложность:

Время: O(n) — один проход
Память: O(1)

#Задача 9: Valid Palindrome II (LeetCode 680) 🟩 Easy

Ссылка: https://leetcode.com/problems/valid-palindrome-ii/

Условие: Дана строка s. Можно удалить не более одного символа. Определите, может ли строка стать палиндромом после удаления.

Примеры:

Ввод: s = "aba" Вывод: true

Ввод: s = "abca" Вывод: true Объяснение: Можно удалить символ 'c'

Ввод: s = "abc" Вывод: false

Ограничения:

1 <= s.length <= 10⁵
s состоит из строчных букв английского алфавита

💡 Подсказка: Используйте стандартную проверку палиндрома. При несовпадении попробуйте два варианта: пропустить left или right. Один из вариантов должен быть палиндромом.

Решение:

def validPalindrome(s):
    def is_palindrome_range(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            # Пробуем удалить либо left, либо right
            return is_palindrome_range(left + 1, right) or \
                   is_palindrome_range(left, right - 1)
        left += 1
        right -= 1
    
    return True

Объяснение:

Стандартная проверка палиндрома
При несовпадении пробуем два варианта: пропустить left или right
Один из вариантов должен быть палиндромом

Сложность:

Время: O(n) — даже с проверкой двух вариантов
Память: O(1)

#Задача 10: 4Sum (LeetCode 18) 🟩 Medium

Ссылка: https://leetcode.com/problems/4sum/

Условие: Дан массив целых чисел nums длины n и целевое значение target. Найдите все уникальные четвёрки [nums[a], nums[b], nums[c], nums[d]], такие что:

0 <= a, b, c, d < n
a, b, c, d различны
nums[a] + nums[b] + nums[c] + nums[d] == target

Верните массив всех уникальных четвёрок. Решение не должно содержать дублирующихся четвёрок.

Примеры:

Ввод: nums = [1, 0, -1, 0, -2, 2], target = 0 Вывод: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Ввод: nums = [2, 2, 2, 2, 2], target = 8 Вывод: [[2, 2, 2, 2]]

Ограничения:

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

💡 Подсказка: Аналогично 3Sum: два внешних цикла для первых двух чисел, Two Pointers для оставшихся двух. Тщательная проверка дубликатов на всех уровнях.

Решение:

def fourSum(nums, target):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 3):
        # Пропускаем дубликаты
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            
            left, right = j + 1, n - 1
            
            while left < right:
                current_sum = nums[i] + nums[j] + nums[left] + nums[right]
                
                if current_sum == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    
                    left += 1
                    right -= 1
                elif current_sum < target:
                    left += 1
                else:
                    right -= 1
    
    return result

Объяснение:

Два внешних цикла для первых двух чисел
Two Pointers для оставшихся двух
Тщательная проверка дубликатов

Сложность:

Время: O(n³)
Память: O(1)

#Задача 11: Trapping Rain Water (LeetCode 42) 🟩 Hard

Ссылка: https://leetcode.com/problems/trapping-rain-water/

Условие: Дан массив неотрицательных целых чисел height, представляющий карту высот, где ширина каждого столбца равна 1. После дождя вода может удерживаться между столбцами.

Вычислите, сколько воды может удержаться после дождя.

Примеры:

Ввод: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Вывод: 6 Объяснение: Вода удерживается в 6 ячейках между столбцами

Ввод: height = [4, 2, 0, 3, 2, 5] Вывод: 9

Ограничения:

n == height.length
1 <= n <= 2 × 10⁴
0 <= height[i] <= 10⁵

💡 Подсказка: Вода над столбцом = min(max_left, max_right) - height[i]. Используйте два указателя, двигая указатель с меньшей высотой. Поддерживайте максимумы с обеих сторон.

Решение (Two Pointers):

def trap(height):
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    
    return water

Объяснение:

Вода над столбцом = min(max_left, max_right) - height[i]
Двигаем указатель с меньшей высотой
Поддерживаем максимумы с обеих сторон
Если height[left] < height[right], то left_max точно ≤ right_max, поэтому вода определяется left_max

Сложность:

Время: O(n)
Память: O(1)

#Задача 12: Backspace String Compare (LeetCode 844) 🟩 Easy

Ссылка: https://leetcode.com/problems/backspace-string-compare/

Условие: Даны две строки s и t. Верните true, если они равны при вводе в пустой текстовый редактор. Символ '#' обозначает backspace (удаление предыдущего символа).

Обратите внимание: если backspace применяется к пустой строке, она остаётся пустой.

Примеры:

Ввод: s = "ab#c", t = "ad#c" Вывод: true Объяснение: Обе строки превращаются в "ac"

Ввод: s = "ab##", t = "c#d#" Вывод: true Объяснение: Обе строки превращаются в ""

Ввод: s = "a#c", t = "b" Вывод: false Объяснение: s превращается в "c", t превращается в "b"

Ограничения:

1 <= s.length, t.length <= 200
s и t содержат только строчные буквы и символы '#'

💡 Подсказка: Идите с конца строки. Функция для нахождения следующего валидного символа учитывает backspace. Сравнивайте посимвольно.

Решение:

def backspaceCompare(s, t):
    def get_next_valid_char_index(string, index):
        backspace_count = 0
        while index >= 0:
            if string[index] == '#':
                backspace_count += 1
            elif backspace_count > 0:
                backspace_count -= 1
            else:
                break
            index -= 1
        return index
    
    i, j = len(s) - 1, len(t) - 1
    
    while i >= 0 or j >= 0:
        i = get_next_valid_char_index(s, i)
        j = get_next_valid_char_index(t, j)
        
        if i >= 0 and j >= 0 and s[i] != t[j]:
            return False
        
        # Если один индекс >= 0, а другой < 0 — строки разной длины
        if (i >= 0) != (j >= 0):
            return False
        
        i -= 1
        j -= 1
    
    return True

Объяснение:

Идём с конца строки
Функция get_next_valid_char_index находит следующий символ, учитывая backspace
Сравниваем посимвольно

Сложность:

Время: O(m + n)
Память: O(1)

#5. ⚠️ Common Mistakes

#❌ Ошибка 1: Неверное условие выхода

Проблема: Использование left <= right вместо left < right для поиска пары.

# ❌ Неправильно
while left <= right:  # Может привести к дублированию элементов
    current = arr[left] + arr[right]
    ...

# ✅ Правильно для поиска пары
while left < right:  # left и right никогда не совпадут
    current = arr[left] + arr[right]
    ...

Почему это неправильно: При left == right мы используем один и тот же элемент дважды, что нарушает условие задачи.

Как обнаружить: Проверьте, может ли решение вернуть один и тот же индекс дважды.

#❌ Ошибка 2: Пропуск проверки границ

Проблема: Доступ к элементу массива без проверки границ.

# ❌ Неправильно — может выйти за границы
while left < right:
    left += 1
    if arr[left] == target:  # left может быть == len(arr)!
        ...

# ✅ Правильно — сначала проверка, потом доступ
while left < right:
    if arr[left] == target:  # Проверка перед увеличением
        ...
    left += 1

Почему это неправильно: В Python это вызовет IndexError, в других языках — неопределённое поведение.

Как обнаружить: Всегда проверяйте, что индекс в диапазоне [0, len(arr)) перед доступом.

#❌ Ошибка 3: Бесконечный цикл

Проблема: Указатели не двигаются при определённых условиях.

# ❌ Неправильно — забыли двигать указатель
while left < right:
    if condition:
        pass  # Забыли left += 1 или right -= 1!
    else:
        right -= 1

# ✅ Правильно — всегда двигаем хотя бы один указатель
while left < right:
    if condition:
        left += 1
    else:
        right -= 1

Почему это неправильно: Если условие всегда истинно, указатель не двигается → бесконечный цикл.

Как обнаружить: Убедитесь, что на каждой итерации хотя бы один указатель изменяется.

#❌ Ошибка 4: Пропуск сортировки для Two Sum

Проблема: Применение Two Pointers к неотсортированному массиву.

# ❌ Неправильно — массив не отсортирован
nums = [3, 2, 4]
target = 6
left, right = 0, len(nums) - 1
# Two Pointers не работает!

# ✅ Правильно — сначала сортировка
nums.sort()  # [2, 3, 4]
left, right = 0, len(nums) - 1
# Теперь Two Pointers работает

Почему это неправильно: Two Pointers полагается на монотонность: движение left увеличивает сумму, right — уменьшает.

Как обнаружить: Если массив не отсортирован, либо сортируйте, либо используйте Hash Map.

#❌ Ошибка 5: Неправильная обработка дубликатов

Проблема: Возврат дублирующихся троек в 3Sum.

# ❌ Неправильно — дубликаты в результате
for i in range(n):
    left, right = i + 1, n - 1
    while left < right:
        if nums[i] + nums[left] + nums[right] == 0:
            result.append([nums[i], nums[left], nums[right]])
            left += 1
            right -= 1

# ✅ Правильно — пропускаем дубликаты
nums.sort()
for i in range(n - 2):
    if i > 0 and nums[i] == nums[i - 1]:  # Пропуск дубликатов
        continue
    left, right = i + 1, n - 1
    while left < right:
        if nums[i] + nums[left] + nums[right] == 0:
            result.append([nums[i], nums[left], nums[right]])
            while left < right and nums[left] == nums[left + 1]:
                left += 1  # Пропуск дубликатов
            while left < right and nums[right] == nums[right - 1]:
                right -= 1
            left += 1
            right -= 1

Почему это неправильно: Одинаковые элементы могут привести к дублирующимся результатам.

Как обнаружить: Проверьте результат на дубликаты. Сортируйте массив и пропускайте одинаковые значения.

#6. 🎯 Попробуйте сами

#Задача для самостоятельного решения

Условие: Дан отсортированный массив целых чисел nums и целевое значение target. Найдите два числа, сумма которых равна target, и верните их значения (не индексы).

Если решения нет, верните [-1, -1].

Пример:

Ввод: nums = [1, 3, 5, 7, 9], target = 12
Вывод: [5, 7]

💡 Подсказка 1

Используйте два указателя: один в начале (left = 0), другой в конце (right = len(nums) - 1).

💡 Подсказка 2

Если сумма меньше target — увеличьте left (нужно больше). Если больше — уменьшите right (нужно меньше).

💡 Подсказка 3

Цикл продолжается, пока left < right. Если нашли — верните [nums[left], nums[right]].

✅ Решение

def two_sum_values(nums, target):
    left, right = 0, len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum == target:
            return [nums[left], nums[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return [-1, -1]

Объяснение:

Два указателя движутся навстречу
Сумма сравнивается с target
Двигаем указатель в зависимости от результата

Сложность:

Время: O(n)
Память: O(1)

#7. Шпаргалка

Задача	Паттерн	Ключевая идея
Two Sum II	Навстречу	Сумма краёв, двигаем к цели
Valid Palindrome	Навстречу	Сравнение с пропусками
Container With Most Water	Навстречу	Двигаем меньшую высоту
3Sum/4Sum	Навстречу	Фиксация + Two Sum
Remove Duplicates	Fast & Slow	Копирование уникальных
Move Zeroes	Fast & Slow	Сжатие ненулевых
Sort Colors	Три указателя	Dutch National Flag
Trapping Rain Water	Навстречу	Вода = min(max_left, max_right)

#7. Заключение

Two Pointers — фундаментальный паттерн, который:

Уменьшает сложность с O(n²) до O(n)
Требует O(1) дополнительной памяти
Применим к десяткам классических задач

Ключ к успеху:

Распознать задачу (отсортированный массив, палиндром, слияние)
Выбрать тип движения (навстречу или в одном направлении)
Правильно определить условие движения указателей

Тип

Описание

Пример

Навстречу

left от начала, right от конца, движутся к центру

Two Sum в отсортированном массиве

В одном направлении

Оба движутся слева направо, fast опережает slow

Удаление дубликатов

Разные скорости

slow += 1, fast += 2

Поиск середины (Floyd's Algorithm)

Массив: [2, 7, 11, 15], target = 9 Шаг 1: Шаг 2: ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ │ 2 │ 7 │ 11│ 15│ │ 2 │ 7 │ 11│ 15│ └───┴───┴───┴───┘ └───┴───┴───┴───┘ ↑ ↑ ↑ ↑ left=0 right=3 left=0 right=2 sum = 17 > 9 → sum = 13 > 9 → right-- right-- Шаг 3: Шаг 4 (НАЙДЕНО): ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ │ 2 │ 7 │ 11│ 15│ │ 2 │ 7 │ 11│ 15│ └───┴───┴───┴───┘ └───┴───┴───┴───┘ ↑ ↑ ↑ ↑ left=0 right=1 left=0 right=1 sum = 9 == 9 ✓ return [1, 2] (1-based)

height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Шаг 1 (максимальная ширина): 8 │ │ 7 │ │ │ 6 │ │ │ 5 │ │ │ │ │ 4 │ │ │ │ │ │ 3 │ │ │ │ │ │ │ │ 2 │ │ │ │ │ │ │ │ │ 1 │ │ │ │ │ │ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┴───┴───┘ ↑ ↑ left=0 right=8 width = 8, h = min(1,7) = 1 area = 8 × 1 = 8 Шаг 2 (двинули left, т.к. height[left] < height[right]): 8 │ │ 7 │ │ │ 6 │ │ │ 5 │ │ │ │ │ 4 │ │ │ │ │ │ 3 │ │ │ │ │ │ │ │ 2 │ │ │ │ │ │ │ │ │ 1 │ │ │ │ │ │ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┴───┴───┘ ↑ ↑ left=1 right=8 width = 7, h = min(8,7) = 7 area = 7 × 7 = 49 ← МАКСИМУМ!

Задача

Паттерн

Ключевая идея

Two Sum II

Навстречу

Сумма краёв, двигаем к цели

Valid Palindrome

Навстречу

Сравнение с пропусками

Container With Most Water

Навстречу

Двигаем меньшую высоту

3Sum/4Sum

Навстречу

Фиксация + Two Sum

Remove Duplicates

Fast & Slow

Копирование уникальных

Move Zeroes

Fast & Slow

Сжатие ненулевых

Sort Colors

Три указателя

Dutch National Flag

Trapping Rain Water

Навстречу

Вода = min(max_left, max_right)