Subarray Sum Equals K

Средняя№560сумма подмассива

Дан массив целых чисел, среди них бывают отрицательные, и число k. Нужно посчитать непрерывные подмассивы, сумма которых ровно k. Наш пример: [1, 2, -1, 3, -2, 2] и k = 3 — ответ 4: [1, 2], [3], [3, -2, 2] и [1, 2, -1, 3, -2].

560 Subarray Sum Equals KРазбор · 1×

Пример: [1, 2, -1, 3, -2, 2], k = 3. Под числами — суммы с начала: префикс j стоит перед nums[j]; скобка отмечает найденный подмассив.

numsprefix12-13-22
ещё не дошлиуже пройденотекущеепрошлый префикс, равный needподмассив с суммой k

Пока ничего не нашли: count = 0

01/38
сначала · назад · пуск · шаг
Скорость
1function subarraySum(nums, k):
2 count = 0
3 prefix = 0
4 seen = map {0: 1} // missing keys: 0
5 for each x in nums:
6 prefix = prefix + x
7 need = prefix - k
8 if need in seen:
9 count = count + seen[need]
10 seen[prefix] = seen[prefix] + 1
11 return count
состояние
count
0
prefix
–
seen
–
x
–
need
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Сумма подмассива — это сумма с начала до его конца минус сумма до его начала. Значит, подмассив, который кончается здесь, даёт k ровно тогда, когда раньше был префикс prefix − k, а seen говорит, сколько таких префиксов было.
  2. seen начинается с {0: 1} — пустого префикса до индекса 0. Без него [1, 2] и [1, 2, -1, 3, -2], которые начинаются с индекса 0, не посчитались бы.
  3. Из-за отрицательных чисел не работает скользящее окно: сумма падает и снова растёт, как в [1, 2, -1, 3, -2]. Разности префиксов знаки не мешают.

Сложность

Время O(n): один проход, а поиск и запись в словаре в среднем O(1). Память O(n): в seen может оказаться n + 1 разных префиксов.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.