4. Subarray Sum Equals K

«Преобразование уравнения часто преобразует и сам алгоритм: то, что казалось тяжелым поиском в будущем, оказывается простым взглядом в сохраненное прошлое».
— Кен Томпсон

💡 Связанные темы:

• 1. Теория. Префиксные суммы — базовая формула разности префиксов
• 5. Continuous Subarray Sum — расширение идеи на модульную арифметику
• 6. Maximum Size Subarray Sum Equals K — поиск самого длинного подмассива
• Two Sum — идеологический родственник в мире хеш-таблиц

Введение: Инверсия мышления

Задача Subarray Sum Equals K (LeetCode 560) — одна из самых частых и любимых задач на технических интервью в бигтех (Яндекс, Google, Meta).
На первый взгляд, формулировка звучит обманчиво просто:

Дан массив целых чисел nums и число k. Найти количество непрерывных подмассивов, сумма элементов которых равна k.

Первый рефлекс инженера: «Сумма подмассива? Давайте запустим скользящее окно с двумя указателями!».
И это главная ловушка: в массиве могут присутствовать отрицательные числа. Как только в данных появляются минусы, свойство монотонности рушится: при расширении окна сумма может уменьшиться, а при сужении — увеличиться. Скользящее окно здесь бессильно.

Решение кроется в союзе двух фундаментальных концепций: префиксных сумм и хеш-таблицы.

🎯 Вопросы для уточнения условий (Interview Warm-up)

1. Знаки чисел:
   «Могут ли элементы массива быть отрицательными или нулями?»
   (Да! Именно поэтому Two Pointers и Sliding Window не работают, требуется хеш-таблица).
2. Значение $k$:
   «Может ли само целевое число $k$ быть отрицательным или равным нулю?»
   (Да, $k$ может быть любым).
3. Размер массива и переполнение:
   «Какова длина массива ($N \le 2 \cdot 10^4$) и диапазон чисел? Может ли сумма переполнить 32-битный int?»
   (В Go для накопителя всегда надежнее брать int64).

Инверсия математической формулы

Вспомним базовую формулу префиксных сумм из 1. Теория. Префиксные суммы: сумма подмассива с индекса $i$ по $j$ выражается как:
$$\text{Sum}(i, j) = P[j+1] - P[i]$$

По условию задачи эта сумма обязана равняться $k$:
$$P[j+1] - P[i] = k$$

Перенесем слагаемые:
$$P[i] = P[j+1] - k$$

Ключевой инсайт:
Находясь на текущем шаге $j$ с накопленной суммой $P[j+1]$, нам не нужно перебирать все возможные левые границы $i$. Нам достаточно спросить у истории:

«Сколько раз ранее мы встречали префиксную сумму, равную точно $(P[j+1] - k)$?»

Каждое такое прошлое вхождение дает валидный подмассив, заканчивающийся прямо здесь!

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:2px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc

    A["Шаг j: текущая сумма currentSum = P"]:::entry --> B["Ищем в мапе значение (P - k)"]:::process
    B --> C{"Было ли в истории (P - k)?"}:::accent
    C -- "Да, встретилось M раз" --> D["count += M<br/>(найдено M валидных подмассивов)"]:::success
    C -- "Нет" --> E["count не меняется"]:::process
    D --> F["Увеличиваем счетчик текущей суммы:<br/>freq[P]++"]:::warning
    E --> F
  

🛠️ Оптимальное решение на Go

package subarrsum

// SubarraySum возвращает число непрерывных подмассивов с суммой k.
// Сложность: O(N) по времени, O(N) по памяти.
func SubarraySum(nums []int, k int) int {
    count := 0
    var currentSum int64 = 0

    // freq хранит соответствие: префиксная сумма -> сколько раз она встретилась
    // Преаллокация снижает оверхед на рехеширование мапы
    freq := make(map[int64]int, len(nums)+1)

    // КРИТИЧЕСКИЙ ИНВАРИАНТ:
    // Пустой префикс (до начала массива) имеет сумму 0 и встретился ровно 1 раз!
    freq[0] = 1

    target := int64(k)
    for _, num := range nums {
        currentSum += int64(num)

        // Ищем в истории префикс P[i] = currentSum - target
        needed := currentSum - target
        if times, ok := freq[needed]; ok {
            count += times
        }

        // Регистрируем текущую префиксную сумму
        freq[currentSum]++
    }

    return count
}

🛑 Главная ловушка собеседования: freq[0] = 1

⚙️ Mechanical Sympathy: Память и хеш-таблицы в Go

🏭 Практическое применение в продакшене

1. Детекция аномалий и фрода в платежах:
   Поток банковских транзакций (пополнения со знаком $+$, списания со знаком $-$). Нужно мгновенно отловить последовательность операций, которая в сумме дает $0$ (фиктивные транзакции для накрутки кэшбэка) или подозрительную круглую сумму.
2. Балансировка очередей сообщений:
   Анализ накопленного лага между продюсерами и консьюмерами в топиках Kafka.

💡 Вопросы для самопроверки

🗺️ Навигация