Subarray Sum Matches — Problem Statement & Solution Guide
Problem Description
Given an array of integers nums and an integer target, determine how many contiguous subarrays of nums have a sum equal to target. A subarray is defined as a sequence of consecutive elements taken from the original array. The task is to output a single integer representing the total count of such subarrays.
**Input format**:
- The first line contains a single integer n, the length of the array.
- The second line contains n space‑separated integers representing the elements of nums.
- The third line contains the integer target.
**Output format**:
- Output one integer: the number of contiguous subarrays whose sum equals target.
The solution must handle large inputs efficiently, as the array length can be up to 100,000 elements.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Subarray Sum Matches"
WHY DOES IT MATTER?
The prefix‑sum + hashmap pattern is a cornerstone for any problem that asks for the count of sub‑structures defined by a sum or difference condition. Mastery of this pattern unlocks efficient solutions for a wide range of interview questions, from subarray sums to sub‑matrix sums in 2‑D grids.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the sum of a contiguous segment can be expressed as a difference of two cumulative totals, allowing us to replace nested loops with a single pass that updates a frequency map of previously seen totals.
REAL-WORLD CONNECTION
In distributed logging systems, each log entry can be treated as a numeric event; detecting a sequence of events that together reach a specific threshold (e.g., total transaction amount) mirrors the subarray‑sum problem, where prefix sums act like cumulative counters across time‑ordered streams.
During an interview, compute the running sum on the fly, update the hashmap before moving to the next element, and remember to increment the answer by the count of (currentSum – target) already in the map; this order avoids off‑by‑one errors.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The Subarray Sum Equals Target problem is a classic illustration of prefix‑sum techniques combined with hash‑map look‑ups. By converting the original array into a running cumulative sum, each subarray sum can be expressed as the difference between two prefix sums, i.e., sum(i..j) = prefix[j] – prefix[i‑1]. This observation transforms a potentially O(n²) enumeration into a counting problem: for each current prefix value we need to know how many earlier prefixes equal (currentPrefix – target). A hash map storing frequencies of previously seen prefix sums enables constant‑time queries, yielding a linear‑time solution. Naïve double‑loop methods fail on large inputs because they recompute overlapping sums repeatedly, leading to quadratic time that exceeds typical constraints (n up to 10⁵ or more). The optimal paradigm—prefix sum + hashmap—leverages the additive property of integers and the O(1) average lookup of hash tables to achieve O(n) time and O(n) auxiliary space, making it suitable for real‑world high‑throughput systems.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain very large integers that might cause prefix sum overflow?
Use a 64‑bit integer type (e.g., long long in C++ or Python's arbitrary‑precision int) for the cumulative sum and hashmap keys; alternatively, apply modular arithmetic if the problem statement permits a modulus, ensuring overflow is avoided while preserving the difference property.
Q2Can you extend the algorithm to count subarrays whose sum is divisible by k?
Yes. Store frequencies of prefix sums modulo k; for each new prefix, the number of earlier prefixes with the same modulo value gives the count of subarrays whose sum is divisible by k, because (prefix[j] – prefix[i]) % k == 0 ⇔ prefix[j] % k == prefix[i] % k.
Q3What is the time‑space trade‑off if you are constrained to O(1) extra space?
With O(1) extra space you must revert to the brute‑force O(n²) method or use a sliding‑window technique that only works for non‑negative numbers; otherwise, you cannot achieve linear time without storing prefix frequencies.
Examples
Input
5 1 2 3 4 5 5
Output
2
Explanation: The subarrays that sum to 5 are [5] (indices 4‑4) and [2,3] (indices 1‑2). No other contiguous segment sums to 5, so the answer is 2.
Input
4 1 -1 1 -1 0
Output
4
Explanation: All subarrays with sum 0 are: 1. indices 0‑1: [1, -1] 2. indices 0‑3: [1, -1, 1, -1] 3. indices 1‑2: [-1, 1] 4. indices 2‑3: [1, -1] Thus the count is 4.
Input
3 0 0 0 0
Output
6
Explanation: Every possible subarray of the array [0,0,0] sums to 0. There are 3*(3+1)/2 = 6 such subarrays: [0] (0‑0), [0] (1‑1), [0] (2‑2), [0,0] (0‑1), [0,0] (1‑2), and [0,0,0] (0‑2).
Constraints
- 1 <= n <= 100000
- -1000000000 <= nums[i] <= 1000000000
- -100000000000000 <= target <= 100000000000000
- The sum of all elements in any subarray fits within a 64‑bit signed integer.
Optimal Approach & Strategy
Maintain a running prefix sum and a hash map of its frequencies; for each element, add the count of (prefixSum – target) from the map to the answer, then update the map with the current prefix sum.
Brute Force Approach
Iterate over all possible start indices, then for each start, expand the end index while accumulating the sum, checking if it equals the target; this requires two nested loops.
Verified Code Solutions
function solution(nums, targetSum) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
let currentSum = 0;
for (let j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum === targetSum) {
count++;
}
}
}
return count;
}class Solution {
public:
int solution(vector<int>& nums, int targetSum) {
int count = 0;
for (int i = 0; i < nums.size(); i++) {
int currentSum = 0;
for (int j = i; j < nums.size(); j++) {
currentSum += nums[j];
if (currentSum == targetSum) {
count++;
}
}
}
return count;
}
};class Solution {
public int solution(int[] nums, int targetSum) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int currentSum = 0;
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum == targetSum) {
count++;
}
}
}
return count;
}
}def solution(nums, targetSum):
count = 0
for i in range(len(nums)):
currentSum = 0
for j in range(i, len(nums)):
currentSum += nums[j]
if currentSum == targetSum:
count += 1
return countfunction solution(nums, targetSum) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
let currentSum = 0;
for (let j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum === targetSum) {
count++;
}
}
}
return 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.