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

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

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

## Ответ

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

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

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

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../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)