Subarray Sum Equals K
Understanding the Problem
We need to count every contiguous subarray that sums to exactly k. The task is the total count, not a single subarray or the longest one.
A subarray is defined by its start and end indices. For an array of length n, there are n * (n + 1) / 2 possible subarrays. The brute force approach checks every single one, but can we do better?
There is a faster way using cumulative sums. If we know the cumulative sum from index 0 to index j (call it prefixSum[j]), and the cumulative sum from index 0 to some earlier index i (call it prefixSum[i]), then the sum of the subarray from i+1 to j is prefixSum[j] - prefixSum[i]. When that difference equals k, the subarray is valid. So for each position j, we count how many earlier prefix sums equal prefixSum[j] - k.
Key Constraints:
nums.lengthup to2 * 10^4puts O(n^2) at about4 * 10^8operations in the worst case, which is too slow, so an O(n) solution is preferred- Elements can be negative (
-1000 <= nums[i] <= 1000), which rules out sliding window approaches that rely on the sum growing as the window expands kcan be negative too, so we cannot assume anything about the target sum's sign
Approach 1: Brute Force
Intuition
Try every possible subarray, compute its sum, and check if it equals k. We fix a starting index i, then extend the subarray one element at a time to each ending index j. Keeping a running sum as we extend avoids recomputing the sum from scratch each time.
Algorithm
- Initialize a counter
countto 0 - For each starting index
ifrom 0 to n-1: - Initialize
sumto 0 - For each ending index
jfromito n-1: - Add
nums[j]tosum - If
sumequalsk, incrementcount - Return
count
Example Walkthrough
Code
- Time Complexity: O(n^2). We have two nested loops. The outer loop runs
ntimes, and for each iteration, the inner loop runs up tontimes. Each inner iteration does O(1) work. - Space Complexity: O(1). We only use a few integer variables regardless of input size.
The repeated forward scans are the cost. The next approach computes the prefix sum in a single pass and uses a hash map to look up, in O(1), how many earlier prefix sums form a valid subarray ending at the current position.
Approach 2: Prefix Sum + Hash Map
Intuition
The sum of a subarray from index i+1 to index j equals prefixSum[j] - prefixSum[i]. For this to equal k, we need prefixSum[i] = prefixSum[j] - k. So as we walk through the array building up the prefix sum, at each position j we count how many earlier prefix sums equal currentPrefixSum - k.
We track those frequencies in a hash map and initialize it with {0: 1}. That entry accounts for subarrays starting at index 0, where the prefix sum itself equals k (and prefixSum - k is therefore 0).
The prefix sum turns "find subarrays with sum k" into "find pairs of prefix sums that differ by k," which mirrors Two Sum with a difference instead of an addition. Because we record each prefix sum only after using it for the lookup, every match pairs the current index with a strictly earlier one, so each counted subarray is non-empty and counted exactly once.
The {0: 1} seed covers subarrays starting at index 0. With nums = [3], k = 3, the prefix sum after the first element is 3, and we need prefixSum - k = 0 in the map to count it. Seeding 0 once provides that match.
Algorithm
- Initialize
count = 0,prefixSum = 0, and a hash mapprefixCountwith{0: 1} - For each element
numin the array: - Add
numtoprefixSum - If
prefixSum - kexists inprefixCount, add its frequency tocount - Increment
prefixCount[prefixSum]by 1 - Return
count
Example Walkthrough
Code
- Time Complexity: O(n). We make a single pass through the array. At each element, we do one hash map lookup and one hash map insert, both O(1) on average.
- Space Complexity: O(n). In the worst case, every prefix sum is unique, so the hash map stores
n + 1entries (including the initial{0: 1}).