Given an array of integers (which may include negative numbers) and an integer k, find the total number of contiguous subarrays whose elements sum to k.
For example, given nums = [1, 1, 1] and k = 2, the output is 2 because the subarrays [1, 1] (indices 0-1) and [1, 1] (indices 1-2) both sum to 2.
Explain your approach, why a sliding window does not work here, and analyze the time and space complexity.
How to approach it
- Hint 1
A brute force approach checks all subarrays in O(n^2). Can you do better?
- Hint 2
Think about prefix sums: the sum of subarray [i, j] equals prefix[j+1] - prefix[i]. When does this equal k?
- Hint 3
If prefix[j] - k = prefix[i] for some earlier index i, then the subarray from i to j sums to k. A hash map of prefix sum frequencies makes this O(n).
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.