Subarray Sum Matches 2 — Problem Statement & Solution Guide
Problem Description
Given an integer array nums and an integer k, determine how many contiguous sub‑segments of nums have a sum exactly equal to k. A sub‑segment (or subarray) is defined by a pair of indices (i, j) with 0 ≤ i ≤ j < nums.length, and its sum is the total of all elements from nums[i] through nums[j] inclusive. Return the total count of such sub‑segments. The solution must run in linear time relative to the length of the array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Subarray Sum Matches 2"
WHY DOES IT MATTER?
Counting sub‑arrays with a target sum is a fundamental pattern that appears in database query optimization, financial transaction analysis, and real‑time monitoring dashboards. Mastering the prefix‑sum + hashmap technique equips engineers to solve a broad class of range‑query problems efficiently.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the sub‑array sum condition can be rewritten as a difference of two prefix sums. By counting how many previous prefix sums satisfy P[current]‑k, we replace a nested loop with a constant‑time hashmap lookup, collapsing O(n²) work into O(n).
REAL-WORLD CONNECTION
Think of a streaming log processor that needs to detect when the cumulative number of events reaches a specific threshold within any sliding time window. By storing timestamps of cumulative counts (prefix sums) in a hash map, the system can instantly determine how many windows hit the exact threshold without re‑scanning the log.
During the interview, compute the running prefix sum on the fly and update the hashmap *before* moving to the next element. This order ensures that sub‑arrays starting at index 0 are counted correctly and avoids off‑by‑one errors.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The classic way to count sub‑arrays whose sum equals a target k is to use prefix sums. A prefix sum P[i] represents the total of the first i elements (0‑based, with P[0]=0). The sum of any sub‑array nums[i..j] can be expressed as P[j+1]‑P[i]. Therefore, for each ending index j we need to know how many earlier prefix sums equal P[j+1]‑k. By storing the frequencies of all prefix sums seen so far in a hash map, we can retrieve this count in O(1) time per element, yielding an overall linear solution.
A naïve double‑loop enumerates every (i, j) pair, computes the sub‑array sum, and checks against k. This approach runs in O(n²) time and quickly exceeds time limits for n up to 10⁵ or larger, which is typical in interview constraints. Moreover, repeated recomputation of sums wastes memory bandwidth. The optimal paradigm—prefix‑sum + hashmap—leverages the additive property of sums and constant‑time look‑ups to collapse the quadratic search space into a single pass.
The underlying mathematical insight is that the difference of two prefix sums equals the sum of the segment between them. By counting occurrences of each prefix sum as we scan the array, we transform the problem into counting pairs of equal‑difference values, a classic use‑case for frequency maps. This technique generalizes to many “sub‑array with target” problems, making it a cornerstone pattern in array‑based interview questions.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain very large integers that might cause integer overflow when computing prefix sums?
Use a 64‑bit integer type (e.g., long long in C++ or long in Java) for the running prefix sum and the hashmap keys. If the language supports arbitrary‑precision integers (like Python's int), you can rely on them directly. The algorithmic steps remain unchanged.
Q2Can you adapt the algorithm to count sub‑arrays with sum **at most** k instead of exactly k?
Yes. Maintain a sorted data structure (e.g., Balanced BST or Fenwick Tree) of prefix sums seen so far. For each new prefix sum P, you need the count of earlier prefixes ≥ P‑k, which can be obtained via order‑statistics queries in O(log n) time, leading to O(n log n) overall.
Q3Why does the hashmap solution work even when the array contains negative numbers, whereas a sliding‑window two‑pointer technique fails?
The sliding‑window method relies on the monotonic increase of the window sum, which only holds for non‑negative numbers. Negative values can cause the sum to decrease when expanding the window, breaking the invariant. The hashmap approach does not depend on monotonicity; it only uses the additive property of prefix sums, so it correctly handles any integer values.
Examples
Input
6 5 1 2 3 2 1 4
Output
3
Explanation: All sub‑segments whose sum equals 5 are: 1. indices [0,1] → 1+2 = 3 (not 5) 2. indices [0,2] → 1+2+3 = 6 (not 5) 3. indices [1,2] → 2+3 = 5 ✅ 4. indices [2,3] → 3+2 = 5 ✅ 5. indices [3,4] → 2+1 = 3 (not 5) 6. indices [4,5] → 1+4 = 5 ✅ Thus three sub‑segments meet the requirement, so the answer is 3.
Input
4 -2 -1 -1 2 -2
Output
2
Explanation: Sub‑segments with sum -2 are: - indices [0,1] → -1 + -1 = -2 ✅ - indices [3,3] → -2 = -2 ✅ No other contiguous range adds to -2, giving a total of 2.
Input
8 0 0 1 -1 2 -2 3 -3 0
Output
6
Explanation: The sub‑segments whose sum equals 0 are: 1. [0,0] → 0 ✅ 2. [0,2] → 0+1-1 = 0 ✅ 3. [1,2] → 1-1 = 0 ✅ 4. [3,4] → 2-2 = 0 ✅ 5. [5,6] → 3-3 = 0 ✅ 6. [7,7] → 0 ✅ Hence the answer is 6.
Constraints
- 1 <= nums.length <= 100000
- -10^9 <= nums[i] <= 10^9
- -10^9 <= k <= 10^9
- The algorithm should use O(n) time and O(n) auxiliary space at most.
Optimal Approach & Strategy
Maintain a hash map of prefix‑sum frequencies while scanning the array once; for each element, add the count of (currentPrefix‑k) to the answer and then increment the frequency of currentPrefix. This yields O(n) time and O(n) space.
Brute Force Approach
Iterate over every possible start index i, then for each i sum elements forward to every end index j, checking if the sum equals k. This double loop is O(n²).
Verified Code Solutions
function solution(nums, target) {
let hashmap = {0: 1};
let count = 0;
let cumulativeSum = 0;
for (let num of nums) {
cumulativeSum += num;
if (hashmap[cumulativeSum - target]) {
count += hashmap[cumulativeSum - target];
}
hashmap[cumulativeSum] = (hashmap[cumulativeSum] || 0) + 1;
}
return cumulativeSum > target ? 0 : count;
}class Solution {
public:
int solution(vector<int>& nums, int target) {
unordered_map<int, int> hashmap;
hashmap[0] = 1;
int count = 0;
int cumulativeSum = 0;
for (int num : nums) {
cumulativeSum += num;
if (hashmap.find(cumulativeSum - target) != hashmap.end()) {
count += hashmap[cumulativeSum - target];
}
hashmap[cumulativeSum] = hashmap[cumulativeSum] + 1;
}
return cumulativeSum > target ? 0 : count;
}
};class Solution {
public int solution(int[] nums, int target) {
HashMap<Integer, Integer> hashmap = new HashMap<>();
hashmap.put(0, 1);
int count = 0;
int cumulativeSum = 0;
for (int num : nums) {
cumulativeSum += num;
if (hashmap.containsKey(cumulativeSum - target)) {
count += hashmap.get(cumulativeSum - target);
}
hashmap.put(cumulativeSum, hashmap.getOrDefault(cumulativeSum, 0) + 1);
}
return cumulativeSum > target ? 0 : count;
}
}def solution(nums, target):
hashmap = {0: 1}
count = 0
cumulativeSum = 0
for num in nums:
cumulativeSum += num
if cumulativeSum - target in hashmap:
count += hashmap[cumulativeSum - target]
hashmap[cumulativeSum] = hashmap.get(cumulativeSum, 0) + 1
return 0 if cumulativeSum > target else countfunction solution(nums, target) {
let hashmap = {0: 1};
let count = 0;
let cumulativeSum = 0;
for (let num of nums) {
cumulativeSum += num;
if (hashmap[cumulativeSum - target]) {
count += hashmap[cumulativeSum - target];
}
hashmap[cumulativeSum] = (hashmap[cumulativeSum] || 0) + 1;
}
return cumulativeSum > target ? 0 : count;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.