Topic 27 of 30 · Intermediate
Count contiguous subarrays summing to K
Return the number of nonempty contiguous subarrays whose sum equals K.
IntermediateJunior · 1–3 yearsPrefix sum
Java 17+; compile each complete program as Main.java.
Problem statement
Return the number of nonempty contiguous subarrays whose sum equals K.
Count balancing runs of positive and negative ledger adjustments.
Input: int[] and long target.
Output: long count.
- n <= 100000.
- Values within int bounds; long prefix sum is sufficient for this n.
- Negative and zero values allowed.
Sample 1
Input: [1,1,1],2 Output: 2
Two adjacent pairs sum to 2.
Sample 2
Input: [0,0],0 Output: 3
Both singles and their pair qualify.
Brute-force solution
For each start maintain a running sum over all ends.
O(n) expected.
import java.util.*;
class Main {
static long countSubarrays(int[] nums,long k){Map<Long,Long> freq=new HashMap<>();freq.put(0L,1L);long sum=0,result=0;for(int x:nums){sum+=x;result+=freq.getOrDefault(sum-k,0L);freq.merge(sum,1L,Long::sum);}return result;}
public static void main(String[] args) throws Exception {
System.out.println(countSubarrays(new int[]{1,1,1},2));
if(countSubarrays(new int[]{1,1,1},2)!=2 || countSubarrays(new int[]{0,0},0)!=3)throw new AssertionError();
}
}
Optimized solution
Two prefix sums differ by K; count previous occurrences of sum-K.
- Seed prefix zero once.
- Accumulate long sum.
- Count prior complements.
- Record the current prefix after counting.
import java.util.*;
class Main {
static long countSubarrays(int[] nums,long k){Map<Long,Long> freq=new HashMap<>();freq.put(0L,1L);long sum=0,result=0;for(int x:nums){sum+=x;result+=freq.getOrDefault(sum-k,0L);freq.merge(sum,1L,Long::sum);}return result;}
public static void main(String[] args) throws Exception {
System.out.println(countSubarrays(new int[]{1,1,1},2));
if(countSubarrays(new int[]{1,1,1},2)!=2 || countSubarrays(new int[]{0,0},0)!=3)throw new AssertionError();
}
}
Complexity analysis
Time: O(n) expected.
Auxiliary space: O(n)
Test cases
- Zeros.
- Negative values.
- Empty.
Supplied main asserts two cases; also assert countSubarrays(new int[]{-1,1},0)==1.Common mistakes
- Overwriting prefix frequency rather than adding.
- Using sliding windows with negative values.
Key takeaways
- Count repeated prefixes.
- Lookup before recording.
- Use wide arithmetic.
Follow-up challenges
- How would you return ranges rather than a count?
- Why seed the zero prefix?