← Java roadmap

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.

  1. Seed prefix zero once.
  2. Accumulate long sum.
  3. Count prior complements.
  4. 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?
Practise Java with the AI mentor

Can't find a Java topic you need for exams or placements? Request it and we'll add it.