03 · ШАБЛОН ПРОХОДА

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

Два индекса заменяют вложенный перебор, когда данные упорядочены или сравниваются с двух сторон.

3 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Индексы

left, right := 0, len(nums)-1
for left < right {
    // сдвинуть одну из границ
}

Указатели здесь — индексы int, а не *int.

Обмен

nums[left], nums[right] =
    nums[right], nums[left]

Множественное присваивание не требует временной переменной.

Fast / slow

for fast < len(nums) {
    if keep(nums[fast]) {
        nums[slow] = nums[fast]
        slow++
    }
    fast++
}

Подходит для фильтрации массива на месте.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Сумма в отсортированном массиве

Сумма мала — двигаем left, велика — right.

O(n) time · O(1) space

solution.go

func twoSumSorted(nums []int, target int) []int {
    left, right := 0, len(nums)-1
    for left < right {
        sum := nums[left] + nums[right]
        if sum == target { return []int{left, right} }
        if sum < target { left++ } else { right-- }
    }
    return nil
}

ПРИМЕР РЕШЕНИЯ

Палиндром

Пропускаем неалфавитные символы и сравниваем края.

O(n) time · O(1) space

solution.go

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1
    for left < right {
        for left < right && !isAlphaNum(s[left]) { left++ }
        for left < right && !isAlphaNum(s[right]) { right-- }
        if toLower(s[left]) != toLower(s[right]) { return false }
        left++; right--
    }
    return true
}

ПРИМЕР РЕШЕНИЯ

Контейнер с водой

Площадь ограничена меньшей стенкой — её и двигаем.

O(n) time · O(1) space

solution.go

func maxArea(h []int) int {
    left, right, best := 0, len(h)-1, 0
    for left < right {
        best = max(best, min(h[left], h[right])*(right-left))
        if h[left] < h[right] { left++ } else { right-- }
    }
    return best
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Есть ли сортировка или монотонность
Что означает каждый указатель
Почему каждый индекс движется только вперёд