Count subarrays that sum to k

Question

Given an integer array nums (values may be negative) and a target k, count the number of contiguous subarrays whose elements sum to exactly k. Target O(n) time. Sliding windows do not work here, negatives mean a window's sum is not monotonic.

Accepted Answer

Because negatives rule out the two-pointer window, use prefix sums with a hash map of counts. Maintain the running prefix sum s. For the current position, every earlier prefix equal to s - k marks the start of a subarray ending here summing to k, so add the stored count of s - k. Then record s itself. Seed the map with {0: 1} to account for subarrays that start at index 0 (a prefix equal to k on its own). Tracing nums = [1, 1, 1], k = 2: prefix sums run 1, 2, 3. At s = 2 we look for s - k = 0, found once → count = 1; at s = 3 we look for 1, found once → count = 2. Answer 2. The [1, -1, 0] cas…

Count subarrays that sum to k

Your answer

More Coding questions