---
title: Subarray Sum Equals K
difficulty: Medium
category: Hash Table
leetcode_id: 560
revision_count: 2
last_revision: 2026-09-12
---

# Subarray Sum Equals K

> **LeetCode:** [#560](https://leetcode.com/problems/subarray-sum-equals-k/)
> **Сложность:** Medium
> **Категория:** Hash Table

## Условие

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

```
Input:  nums = [1,1,1], k = 2          →  Output: 2  // подмассивы: [1,1], [1,1]
Input:  nums = [1,2,3], k = 3          →  Output: 2  // подмассивы: [1,2], [3]
Input:  nums = [1,-1,0], k = 0         →  Output: 3  // подмассивы: [1,-1], [0], [1,-1,0]
```

## Ключевая идея

**Всё строится на одном тождестве: сумма любого подмассива — это разность двух префиксных сумм.**

Префиксная сумма `P(i)` = сумма элементов от начала до индекса `i` включительно (`nums[0] + ... + nums[i]`). Тогда подмассив `[j..i]` имеет сумму:

```
сумма[j..i] = P(i) − P(j−1)
```

Пример: `nums = [1,2,3]` → `P = [1, 3, 6]`. Подмассив `[0..1]` (элементы `[1,2]`) = `P(1) − P(−1) = 3 − 0 = 3`. Здесь `P(−1) = 0` — это «пустой префикс» до начала массива.

**Переформулируем задачу через это тождество.** Нам нужны подмассивы с суммой `k`:

```
P(i) − P(j−1) = k   ⟺   P(j−1) = P(i) − k
```

Читается так: для каждого текущего индекса `i` мы ищем, **сколько раз раньше** уже встречалась префиксная сумма `P(i) − k`. Каждое такое вхождение — это ровно один подмассив, заканчивающийся в `i`, с суммой `k`.

**Зачем хэш-таблица.** Идём по массиву один раз и помним в `freq`, сколько раз каждая префиксная сумма встречалась **до** текущей позиции. На шаге `i`:

```
count += freq[P(i) − k]   # сколько подмассивов заканчивается здесь с суммой k
freq[P(i)] += 1           # запоминаем текущую сумму для будущих позиций
```

**Почему `freq[0] = 1`.** Если подмассив начинается с самого начала (индекса `0`), то `j−1 = −1`, а `P(−1) = 0`. Мы обязаны заранее сказать «пустой префикс со значением 0 уже существует один раз» — иначе потеряем все подмассивы, стартующие от индекса 0. Заодно это покрывает случай `P(i) == k` (тогда `P(i) − k = 0`).

**Порядок строк важен:** сначала считаем `count`, потом записываем в `freq`. Иначе при `k = 0` мы бы «нашли» подмассив нулевой длины (текущая позиция сама с собой).

## Оценка сложности

- **Время:** O(n) — один проход по массиву, операции с хэшем O(1)
- **Память:** O(n) — хэш-таблица хранит до n уникальных префиксных сумм

## Решение (Ruby)

```ruby
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def subarray_sum(nums, k)
  count = 0
  prefix_sum = 0
  freq = Hash.new(0)
  freq[0] = 1

  nums.each do |n|
    prefix_sum += n
    count += freq[prefix_sum - k]
    freq[prefix_sum] += 1
  end

  count
end
```

## Разбор на примере

```
nums = [1, 2, 3], k = 3

Префиксные суммы:  P(-1)=0,  P(0)=1,  P(1)=3,  P(2)=6

Задача = найти пары (ранняя P, текущая P) с разностью k=3:
  i=1: P(1)=3, ищем P(j−1) = 3−3 = 0 → есть (пустой префикс) → подмассив [0..1] = [1,2]
  i=2: P(2)=6, ищем P(j−1) = 6−3 = 3 → есть P(1)             → подмассив [2..2] = [3]

Теперь то же самое шаг за шагом, как это делает код:

freq = {0 => 1}
count = 0, prefix_sum = 0

i=0, n=1: prefix_sum = 1
  freq[1 - 3 = -2] = 0 → count += 0
  freq[1] = 1         → {0 => 1, 1 => 1}

i=1, n=2: prefix_sum = 3
  freq[3 - 3 = 0] = 1 → count += 1  (count=1)  # подмассив [1,2]
  freq[3] = 1         → {0 => 1, 1 => 1, 3 => 1}

i=2, n=3: prefix_sum = 6
  freq[6 - 3 = 3] = 1 → count += 1  (count=2)  # подмассив [3]
  freq[6] = 1         → {0 => 1, 1 => 1, 3 => 1, 6 => 1}

Result: 2
```

## Edge Cases

- **Пустой массив** → `freq[0 - k] = 0` (нет в хэше, `Hash.new(0)` отдаст 0) → `count = 0`.
- **Один элемент**, `nums[0] == k` → `freq[0] = 1` даёт `count = 1` на первом же шаге.
- **Все нули**, `k = 0` → каждый шаг добавляет `freq[0]` (которое растёт: 1, 2, 3, ...) → ответ `n(n+1)/2`.
- **Отрицательные числа** — алгоритму без разницы: `prefix_sum - k` спокойно уходит в минус, хэш-таблица это переваривает.

## Типичные ошибки

1. ❌ **Забыть `freq[0] = 1`** → теряем подмассивы, начинающиеся с индекса 0.
2. ❌ **Обновить `freq` до подсчёта** → при `k = 0` в `freq[prefix_sum]` уже лежит текущий шаг, и мы «находим» подмассив нулевой длины. Порядок: сначала `count += ...`, потом `freq[...] += 1`.
3. ❌ **Вложенные циклы** → O(n²), падает на больших n.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (все подмассивы) | O(n³) | O(1) | Тройной вложенный цикл |
| Cumulative sum (один массив префиксов) | O(n²) | O(n) | Вычисляем сумму каждого подмассива через разность префиксов |
| **Prefix Sum + Hash Map** | **O(n)** | **O(n)** | **Оптимальное решение** — один проход, хэш-таблица |
| Sliding Window | O(n) / O(n²) | O(1) | Работает только для положительных чисел. Для массива с отрицательными — не применим |

## Заметки после повторения

**2026-09-12 — ✅ Понял (раунд 2).** Идея уложилась: сумма подмассива = разность двух префиксных сумм P(i) − P(j−1); ищем пары с разностью k через freq-счётчик; freq[0]=1 — «пустой префикс» для подмассивов от индекса 0. Отвечено на 2: идея верна, но не названы сложность и edge cases.