NeetCode #111LC-560MediumArrays & HashingNC 250
← Back to All Problems#111 · #560 · Subarray Sum Equals K(和为 K 的子数组)
📌 Problem Statement & Constraints
Given an array of integers
nums and an integer k, return the total number of contiguous subarrays whose sum equals k. Constraints: 1 <= nums.length <= 2 * 10^4, -1000 <= nums[i] <= 1000, -10^7 <= k <= 10^7.💡 Core Algorithmic Approaches
- A sliding window fails because the array may contain negative numbers, so the running sum is not monotonic in the window bounds.
- Use prefix sums with a hash map. Let
P[i]be the sum of the firstielements. Thensum(nums[i..j]) = P[j+1] - P[i]. - The condition
P[j+1] - P[i] == kbecomesP[i] == P[j+1] - k. So while scanning, count how many earlier prefix sums equalcurrent - k. - The map stores the frequency of each prefix sum, not just its presence, because multiple earlier prefixes may share the same value.
- Initialise the map with
{0: 1}to represent the empty prefix, which handles subarrays starting at index 0.
💻 Benchmark Python3 Implementation
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
from collections import defaultdict
count = defaultdict(int)
count[0] = 1 # the empty prefix, sum 0, seen once
prefix = 0
res = 0
for x in nums:
prefix += x
# any earlier prefix equal to (prefix - k) closes a valid subarray
res += count[prefix - k]
count[prefix] += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with O(1) average hash operations. The brute-force prefix-sum double loop is O(n^2).
💾 Space Complexity
O(n) for the hash map, which may hold up to n + 1 distinct prefix sums.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting
count[0] = 1: subarrays that start at index 0 would be missed entirely. - Storing booleans instead of counts: two different start indices can share the same prefix sum, and each yields a distinct subarray.
- Using a sliding window: it only works when all values are non-negative, which the constraints do not guarantee.
- Incrementing the prefix count before adding to the result: an element would be allowed to pair with itself, counting empty subarrays when
k == 0. - Assuming
kmust be positive:kcan be negative, and the same algorithm handles it unchanged.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.