round: 4
ticket_no: 04
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-15
---

# Билет 04 — 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
```

Constraints: `1 <= nums.length <= 2 * 10^4`; `-10^3 <= nums[i] <= 10^3`; `-10^7 <= k <= 10^7`.

## Ответ

> Дословно из `work-03-subarray-sum-equals-k.md` (код как написан):

```ruby
def subarray_sum(nums, k)
  result = 0
  freq = Hash.new(0)
  sum = 0

  freq[0] = 1

  nums.each do |num|
    sum += num

    result += freq[k - sum]

    freq[sum] += 1
  end

  result
end

# run: O(n)
# mem: min(O(1)), max(O(n))
```

## Разбор

**Что верно:**
- Идея каноническая и, наконец, правильная (провал R1 закрыт по идее): префиксные суммы + хеш частот + `freq[0] = 1` для подмассивов с начала массива.
- Порядок «сначала проверить, потом вставить текущий префикс» — верный: подмассив непустой, префикс обязан быть строго раньше.
- Время O(n) — названо верно.

**Что упущено и ошибки:**
1. ❌ **Перепутан знак в ключе хеша:** `result += freq[k - sum]`, а должно быть `freq[sum - k]`. Вывод: `sum - p = k` → искомый префикс `p = sum - k`. Прогон: `[1,1,1],k=2 → 1` вместо 2 (первый же пример условия падает), `[1,2,3],k=3 → 1` вместо 2, классика `[3,4,7,2,-3,1,4,2],k=7 → 1` вместо 4. `[1,-1,0],k=0` «прошёл» случайно: при k=0 знак неразличим.
2. ⚠️ **Память записана некорректно:** `min(O(1)), max(O(n))` — так не пишут; хеш может вырасти до n ключей → O(n). Уникальные префиксы дают n записей в худшем случае.
3. ⚠️ **Edge cases не названы:** k=0 с отрицательными (`[1,-1,0]`), одиночный элемент (`[1],k=1→1; [1],k=0→0`), все нули (`[0,0,0],k=0→6` — каждый из 6 подмассивов), смысл `freq[0]=1`.

**Эталонная идея:**
Один проход: `sum += num`; количество подмассивов с суммой k, заканчивающихся здесь, = числу префиксов с суммой `sum - k`, т.е. `freq[sum - k]`; затем `freq[sum] += 1`. Инициализация `freq[0] = 1` — пустой префикс перед началом массива.

**Время:** O(n) — один проход, O(1) на операцию с хешем.

**Память:** O(n) дополнительная — хеш префиксных сумм (до n ключей).

**Граничные случаи:** 1) k=0 с отрицательными `[1,-1,0] → 3`; 2) одиночный элемент `[1], k=1 → 1`, `[1], k=0 → 0`; 3) все нули `[0,0,0], k=0 → 6` (n·(n+1)/2); 4) подмассив с начала массива — зачем `freq[0]=1`; 5) счётчик `result` до 2·10^8 — в Ruby без переполнения.

**Критерии (финально):** идея ✅ · структура данных ✅ · сложность ⚠️ (время верно, память записана как min/max) · граничные случаи ❌

## Пересдача (после фикса)

Исправлен знак в ключе хеша: `freq[k - sum]` → `freq[sum - k]` (вывод: `sum - p = k → p = sum - k`). Прогон: 9/9 OK, включая `[3,4,7,2,-3,1,4,2],k=7 → 4`, `[0,0,0],k=0 → 6`, `[1,-2,1],k=0 → 1`.

Не закрыто: память в комментариях (O(n), а не min/max-запись) и edge cases в ответе — удержали оценку на 2.

**Канон сложности:** O(n) / O(n) — сверить с `complexity-cheat-sheet.md`.

**Канон сложности:** O(n) / O(n) — совпадает с `complexity-cheat-sheet.md`.

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