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

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

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

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

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

Constraints: `1 <= n <= 2*10^4`, `-1000 <= nums[i] <= 1000`, `-10^7 <= k <= 10^7`.

## Ответ

> Ладно, давай так, попробуем. Значит, у нас здесь скользящее окно. Мы берем первый элемент в это окно и начинаем его расширять до тех пор, пока мы либо не достигнем числа К в сумме, либо если его превысим. Как только мы его превысили, это означает, что нам это окно не подходит. Нам нужно сдвигаться. Мы тогда убираем первый элемент оттуда. Вот проверяем наше новое окно на корректность здесь. У нас получается так, как мы накапливали, тогда из этого окна, когда мы его немножко меняем, сдвигаем, нам не нужно его полностью пересчитывать. Нам всего лишь из него нужен элемент вычесть, который мы оттуда выкинули. Ну а когда мы его расширяем, нам нужно добавить в это окно одно число. Поэтому мы получается тут балансируем на этом количестве. То есть мы наращиваем окно до тех пор, пока оно меньше К. Иначе нам пора тут двигаться. То есть мы сдвигаем левый элемент. Мы снова становимся меньше или равны, вот, и начинаем расти, пока не превысим. Вот такая идея.

## Разбор

**Что верно:** идея амортизации суммы окна верная: при сдвиге не пересчитывать сумму, а вычесть ушедший элемент и добавить новый — это O(1) на шаг.

**Что упущено и ошибки:** скользящее окно здесь не работает: в ограничениях есть отрицательные числа (-1000..1000), при них сумма не монотонна по длине окна и правило «превысили k → двигаем левый край» даёт неверный ответ. Кроме того, задача про количество подмассивов, а окно ищет наличие/длину. Контрпример: nums = [1,-1,1], k = 1.

**Эталонная идея:** префиксные суммы + hash-счётчик: freq = Hash.new(0); freq[0] = 1; sum += x; count += freq[sum - k]; freq[sum] += 1. Один проход, O(n). Базовый freq[0] = 1 обязателен.

**Сложность:** время 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)