Subarray Sum Equals K in Java: Explanation & Practice

Count subarrays with sum equal to k

Problem summary

Given an array and integer k, count the number of continuous subarrays whose sum equals k. Use prefix sum with HashMap.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1};
        int k = 2;
        
        // Prefix sum technique:
        // If prefixSum[j] - prefixSum[i] = k, subarray (i,j] sums to k
        // Count how many previous prefix sums equal (current - k)
        // Print: Count: 2
    }
}

Expected output and test cases

[1,1,1], k=2 → [1,1] appears twice
```
Count: 2
```
[1,2,3], k=3 → [1,2] and [3]
```
Count: 2
```
[1], k=0 → none
```
Count: 0
```

Hints

Running sum at index j minus running sum at index i gives sum of subarray (i,j]
If runningSum - k exists in our map, we found a valid subarray
Store count of each prefix sum in HashMap
Initialize map with {0: 1} for subarrays starting from index 0

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler