Mediumprefix-sumhash
Решить задачу Subarray Sum Equals K (LeetCode 560)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 560. Подсчитать contiguous subarrays с суммой k. Prefix sum + hash map. O(n) время, O(n) память.
def subarraySum(nums, k):
count, prefix = 0, 0
seen = {0: 1}
for x in nums:
prefix += x
count += seen.get(prefix - k, 0)
seen[prefix] = seen.get(prefix, 0) + 1
return countИдея: sum nums[i..j] = prefix[j+1] - prefix[i]. Если prefix[j+1] - prefix[i] = k, то prefix[i] = prefix[j+1] - k. Идём слева направо, для каждого prefix считаем сколько раз раньше встречалось prefix - k. seen[0] = 1 — пустой prefix. Brute force O(n²). Этот паттерн мощен для всех subarray sum problems.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.