---
round: 2
ticket_no: 3
source_no: 11
slug: subarray-sum-equals-k
topic: Hash Table
difficulty: Medium
leetcode_id: 560
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 3 — Subarray Sum Equals K

## Условие (как предъявлено)

Дан массив целых чисел `nums` и целое число `k`. Вернуть **количество** непрерывных подмассивов, сумма которых равна `k`.

```
Input:  nums = [1,1,1],   k = 2   →  Output: 2
Input:  nums = [1,2,3],   k = 3   →  Output: 2
Input:  nums = [1,-1,0],  k = 0   →  Output: 3
```

Ограничения: длина массива от 1 до 2·10^4, значения элементов в диапазоне ±1000, `k` в диапазоне ±10^7.

## Ответ

> Так, здесь, когда мы идём по массиву, мы составляем хэшмеп. Вот, хэш-таблицу. Значит, э, в которой есть ключ — это сумма под массивов, сумма элементов под массивов от первого элемента до н-ного, да, вот. Ну, в общем, его так вот, походу, как мы встречаем, до текущего элемента, короче, это сумма линейная. Вот. А значением является, сколько раз мы подобную сумму встретили. Вот. И дальше, когда мы подходим к новому элементу, да, мы смотрим, собственно, у нас комплемент какой-то, сколько нам не хватает до нужного числа. Мы заглядываем в этот хэшмеп и можем, например, найти этот комплемент и видим, что такой комплемент встречался, например, пять раз, то есть это означает, что пять таких комбинаций нам подходит. Предварительно ещё мы туда заполняем комплемент ноль, он единица. Такой он нам нужен. Для чего он нам нужен? Он нам нужен, потому что... Потому на нулевом элементе мы, когда минус один смотрим, да, там как раз нулевая сумма обязательно будет встречаться. Ну, в общем, тоже нам помогает, да, нулевая. Как минимум один раз встречается. Ага. Так. Только единственое, что комплемент мы добираем не до текущего элемента, то есть мы ведём текущую префиксную сумму. Но нет, так как мы на текущем шаге рассчитываем только те подмассивы, которые включают текущий элемент, поэтому.Нет, все-таки, значит, мы на текущем шаге смотрим длину, в общем, сумму от первого элемента до текущего. Вот, и дальше смотрим, сколько нам нужно вычесть из этой суммы, чтобы получить К. И смотрим, сколько таких комплиментов как раз было у нас. Ну, то есть, вот сколько у нас таких префиксных сумм было в нашем хэшме. Вот, то есть, там состав, например, фриквенси. Называем частоту, чистоту встречающихся префиксов, назовём их так, префиксных сумм. В общем, сколько раз, сколько вариантов у нас есть вычесть вот это начало, чтобы вычесть вот эту сумму, мы будем получать вот то, что у нас тут будет получаться.

## Разбор

**Что верно:** Ключевая идея (в раунде 1 было ошибочное «скользящее окно») теперь верна: один проход, хэш-таблица «префиксная сумма → сколько раз встречалась», на каждом шаге прибавляем `freq[prefix - k]`, и предзаполняем `freq[0] = 1` для подмассивов, стартующих с индекса 0. Верно объяснено, зачем нужен нулевой префикс (`P(−1) = 0`).

**Что упущено и ошибки:** Не названа сложность по времени и памяти. Не названы граничные случаи (пустой массив, один элемент, массив из одних нулей при `k=0`, отрицательные числа). В формулировке заметно колебание («комплемент добираем не до текущего элемента… нет, всё-таки»), но итог верный: префиксная сумма до текущего элемента, ищем `prefix − k` среди уже виденных. Порядок «сначала `count +=`, потом `freq[prefix] += 1`» явно не проговорён, но и не нарушен.

**Эталонная идея:** префиксные суммы + хэш со счётчиком: `sum[j..i] = P(i) − P(j−1) = k ⟺ P(j−1) = P(i) − k`; считаем, сколько раз `P(i) − k` встречалась раньше.

**Сложность:** время O(n), память O(n).

**Критерии:** идея ✅ · структура данных ✅ · сложность ❌ · граничные случаи ❌

**Разбор задачи:** [`../../algo-solutions/01-must-have/02-hash-table/11-subarray-sum-equals-k.md`](../../algo-solutions/01-must-have/02-hash-table/11-subarray-sum-equals-k.md)