6. Maximum Size Subarray Sum Equals K

«В поисках максимума самое трудное — не забыть самое первое начало».
— Эдсгер Дейкстра

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

• 4. Subarray Sum Equals K — подсчет общего количества подмассивов
• 5. Continuous Subarray Sum — кратность суммы числу $k$
• 1. Теория. Префиксные суммы — математика префиксных сумм
• 03. Скользящее окно — почему монотонность нарушается при отрицательных числах

Введение: От подсчета количества к максимизации длины

Задача Maximum Size Subarray Sum Equals K (LeetCode 325) — классическое продолжение темы 4. Subarray Sum Equals K.
Если там требовалось подсчитать количество всех валидных подмассивов, то теперь перед нами стоит оптимизационная цель: найти наибольшую длину непрерывного подмассива, дающего в сумме ровно $k$. Если таких подмассивов нет — вернуть 0.

Казалось бы, изменение в условии минимально. Но оно кардинально меняет логику работы с хеш-таблицей!

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

1. Знаки чисел:
   «Могут ли числа быть отрицательными?»
   (Да! Если бы числа были строго положительными, задача решалась бы двумя указателями за $O(1)$ памяти. Отрицательные числа делают необходимым использование префиксных сумм).
2. Что возвращать, если подходящих подмассивов нет?
   (Возвращаем 0).
3. Значение $k$:
   «Может ли $k$ быть равным нулю?»
   (Да! $k=0$ — частый случай: поиск самого длинного отрезка, где положительные и отрицательные числа уравновешивают друг друга).

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

Как и прежде, сумма отрезка от $i$ до $j$ выражается через префиксы:
$$P[j+1] - P[i] = k \implies P[i] = P[j+1] - k$$

Длина подмассива от индекса $i$ до индекса $j$ (включительно) равна:
$$\text{Length} = j - i + 1$$

Чтобы длина была максимальной при текущем фиксированном правом конце $j$, левая граница $i$ обязана быть как можно меньше — то есть находиться как можно ближе к началу массива!

Золотое правило алгоритма:
В хеш-таблице мы сохраняем только самое первое (самое раннее) появление каждой префиксной суммы! Если эта сумма встретится нам снова на более поздних шагах, мы игнорируем ее и сохраняем старый индекс.

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"]:::entry --> B["Ищем в мапе target = currentSum - k"]:::process
    B --> C{"target найден в мапе?"}:::accent
    C -- "Да, на индексе firstIdx" --> D["Длина = j - firstIdx<br/>maxLen = max(maxLen, Длина)"]:::success
    C -- "Нет" --> E["Продолжаем поиск"]:::process
    D --> F{"currentSum уже есть в мапе?"}:::warning
    E --> F
    F -- "Да (уже встречалась)" --> G["НЕ перезаписываем!<br/>Оставляем самый ранний индекс"]:::warning
    F -- "Нет (впервые)" --> H["Сохраняем map[currentSum] = j"]:::process
  

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

package maxsubarr

// MaxSubArrayLen находит максимальную длину подмассива с суммой k.
// Сложность: O(N) по времени, O(N) по памяти.
func MaxSubArrayLen(nums []int, k int) int {
    // firstIndex хранит: префиксная сумма -> самый первый индекс, где она возникла
    firstIndex := make(map[int64]int, len(nums)+1)

    // КРИТИЧЕСКИЙ ИНВАРИАНТ:
    // Пустой префикс с суммой 0 находится "до начала массива" — на индексе -1!
    // Это позволяет подмассиву от 0 до j иметь длину j - (-1) = j + 1.
    firstIndex[0] = -1

    var maxLen int
    var currentSum int64
    targetK := int64(k)

    for j, num := range nums {
        currentSum += int64(num)

        // Ищем в истории префикс P[i] = currentSum - targetK
        needed := currentSum - targetK
        if firstIdx, exists := firstIndex[needed]; exists {
            length := j - firstIdx
            if length > maxLen {
                maxLen = length
            }
        }

        // ВАЖНО: сохраняем индекс только если такой суммы еще не было!
        // Нам нужен самый левый (минимальный) индекс для максимизации длины.
        if _, exists := firstIndex[currentSum]; !exists {
            firstIndex[currentSum] = j
        }
    }

    return maxLen
}

🛑 Главная ловушка: перезапись индекса в мапе

⚙️ Mechanical Sympathy: Внутреннее устройство hmap и кэш

🏭 Практическое применение в System Design

1. Анализ финансовых периодов безубыточности:
   Поиск самого продолжительного непрерывного периода в истории компании, когда операционные доходы и расходы полностью компенсировали друг друга ($k = 0$).
2. Анализ сетевых сессий (TCP Zero Window):
   Поиск максимального окна времени, на протяжении которого подтвержденный объем переданных байт в точности соответствовал квоте буфера приемника.

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

🗺️ Навигация