2. Типовые операции и приёмы
«Мастерство инженера проявляется не в изощрённости редких трюков, а в безупречном и точном владении базовым арсеналом инструментов».
— Брайан Керниган
Теоретический фундамент из лекции 1. Теория. Массивы и строки раскрыл нам механику работы заголовка среза (SliceHeader), аллокаций в куче и неизменяемости строк. Но на реальном техническом собеседовании знание низкоуровневых структур — это лишь половина победы. Вторая половина — это умение мгновенно распознать математическую природу задачи и применить подходящий алгоритмический паттерн.
В этой главе мы систематизируем семь фундаментальных операционных приёмов, которые покрывают свыше 90% задач на массивы и строки. Для каждого приёма мы разберём идиоматичную реализацию на Go, пошаговую физическую модель взаимодействия с памятью процессора и типичные подводные камни.
Карта выбора алгоритмического приёма
flowchart TD
classDef entry fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
classDef accent fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
Start["Задача на массивы или строки"]:::entry --> Q1{"Массив отсортирован<br>или монотонный?"}:::warning
Q1 -->|"Да"| TP["1. Два указателя (Two Pointers)<br>или бинарный поиск slices.BinarySearch"]:::success
Q1 -->|"Нет"| Q2{"Требуется непрерывный<br>подмассив / подстрока?"}:::warning
Q2 -->|"Да"| Q3{"Сумма / длина<br>строго монотонны?"}:::warning
Q3 -->|"Да (только числа > 0)"| SW["2. Скользящее окно (Sliding Window)<br>O(N) time, O(1) space"]:::success
Q3 -->|"Нет (есть числа <= 0)"| PS["3. Префиксные суммы + Хеш-карта<br>O(N) time, O(N) space"]:::process
Q2 -->|"Нет"| Q4{"Поиск пар, частот<br>или анаграмм?"}:::warning
Q4 -->|"Да: ограниченный алфавит"| Arr["4. Массив частот [26]int / [128]int<br>Zero-allocation на стеке"]:::success
Q4 -->|"Да: произвольный ввод"| HM["5. Хеш-карта map[K]V<br>make с предвыделением cap"]:::process
Q4 -->|"Нужен порядок или группировка"| Sort["6. Сортировка как предобработка<br>slices.Sort O(N log N)"]:::accent
Приём 1: Два указателя (Two Pointers)
Один из самых мощных приёмов с асимптотикой $O(N)$ по времени и строгим $O(1)$ по дополнительной памяти.
1. Встречные указатели (Opposite Direction)
Применяется на отсортированных массивах и палиндромах. Левый указатель (left = 0) и правый (right = len-1) движутся навстречу друг другу. На каждом шаге мы отсекаем заведомо неподходящее подмножество:
func twoSumSorted(numbers []int, target int) []int {
left, right := 0, len(numbers)-1
for left < right {
sum := numbers[left] + numbers[right]
switch {
case sum == target:
return []int{left + 1, right + 1}
case sum < target:
left++ // Увеличиваем сумму сдвигом левого края
default:
right-- // Уменьшаем сумму сдвигом правого края
}
}
return nil
}
2. Быстрый и медленный указатели (Fast & Slow / In-place Mutation)
Используется для фильтрации данных без аллокации дополнительного массива. Медленный указатель (write) фиксирует границу валидных данных, а быстрый (read) сканирует входной срез:
func moveZeroes(nums []int) {
write := 0
for read := 0; read < len(nums); read++ {
if nums[read] != 0 {
nums[write], nums[read] = nums[read], nums[write]
write++
}
}
}
Mechanical Sympathy: Доступ к элементам строго последовательный. Процессорный блок prefetcher идеально предсказывает адреса, загружая кэш-линии L1/L2 наперёд, что обеспечивает максимальную скорость шины памяти.
Приём 2: Скользящее окно (Sliding Window)
Паттерн для поиска оптимального непрерывного подмассива или подстроки. Окно задается полуинтервалом [left, right): правый указатель монотонно расширяет окно, а левый сжимает его, как только инвариант нарушается.
func minSubArrayLen(target int, nums []int) int {
left, sum, minLen := 0, 0, math.MaxInt
for right := 0; right < len(nums); right++ {
sum += nums[right] // Расширяем окно вправо
for sum >= target { // Сжимаем окно слева при выполнении условия
curLen := right - left + 1
if curLen < minLen {
minLen = curLen
}
sum -= nums[left]
left++
}
}
if minLen == math.MaxInt {
return 0
}
return minLen
}
Приём 3: Префиксные суммы (Prefix Sums)
Позволяет за $O(1)$ получать сумму на любом произвольном подотрезке [L, R].
Формула: $\text{Sum}(L, R) = \text{Prefix}[R+1] - \text{Prefix}[L]$.
nums := []int{10, 20, 30, 40}
pref := make([]int, len(nums)+1)
for i, v := range nums {
pref[i+1] = pref[i] + v
}
// Сумма элементов nums[1..2] (20 + 30 = 50)
rangeSum := pref[3] - pref[1] // 60 - 10 = 50
Тандем с хеш-картой: Количество подмассивов с суммой K (LeetCode 560)
Если в массиве есть отрицательные числа, мы ищем отрезок, где $\text{Prefix}[R] - \text{Prefix}[L] = K$, что эквивалентно $\text{Prefix}[L] = \text{Prefix}[R] - K$:
func subarraySum(nums []int, k int) int {
count, currentSum := 0, 0
// Базовый случай: префиксная сумма 0 встретилась 1 раз до начала массива
seen := make(map[int]int, len(nums))
seen[0] = 1
for _, x := range nums {
currentSum += x
count += seen[currentSum-k]
seen[currentSum]++
}
return count
}
Приём 4: Частотный словарь — Массив против Map
В задачах на анаграммы, изоморфизм строк и подсчёт частот выбор типа структуры данных определяет производительность:
// ИДЕАЛЬНО (ASCII / Латиница): zero allocation, стек, мгновенное сравнение ==
func isAnagram(s, t string) bool {
if len(s) != len(t) {
return false
}
var counts [26]int
for i := 0; i < len(s); i++ {
counts[s[i]-'a']++
counts[t[i]-'a']--
}
return counts == [26]int{}
}
Если же алфавит произвольный (Unicode), используем map[rune]int, обязательно предвыделяя емкость:
counts := make(map[rune]int, len(s))
Приём 5: In-Place развороты и циклический сдвиг
Многие задачи требуют трансформации среза без выделения дополнительной памяти. Базовым кирпичиком выступает разворот диапазона:
func reverse(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
Алгоритм трех разворотов для циклического сдвига массива на $K$ позиций вправо (Rotate Array):
- Развернуть весь массив целиком;
- Развернуть первые $K$ элементов;
- Развернуть оставшиеся $N - K$ элементов.
Сложность: строго $O(N)$ по времени и $O(1)$ по памяти!
Приём 6: Современная сортировка (slices.Sort Go 1.21+)
Сортировка часто превращает запутанную задачу в элементарную. Начиная с Go 1.21, вместо устаревшего sort.Slice следует использовать оптимизированный дженерик-пакет slices:
import "slices"
nums := []int{5, 2, 6, 3, 1, 4}
slices.Sort(nums) // In-place pdqsort за O(N log N), zero-allocation!
// Бинарный поиск в отсортированном срезе:
idx, found := slices.BinarySearch(nums, 3)
Резюме
Семь базовых приёмов — два указателя, скользящее окно, префиксные суммы, частотный массив, in-place развороты, предварительная сортировка и сборка через strings.Builder — образуют универсальный арсенал бэкенд-инженера.
В следующей статье мы применим эти навыки к разбору классической задачи, с которой начинается путь любого разработчика на LeetCode: 3. Two Sum.