Subarray Sum Equals K Using Hash Map in DSA Java

Mental Model

We track sums of numbers from the start to each position and use a map to find if a previous sum lets us form a subarray summing to k.

Analogy: Imagine walking along a path and counting steps. If you know the total steps at two points, the difference tells you how many steps you took between them. We use a map to remember these counts to quickly find matching distances.

Array: [1, 2, 3, 4]
Prefix sums: [0, 1, 3, 6, 10]
Map stores sums seen so far:
{0:1} -> {0:1, 1:1} -> {0:1, 1:1, 3:1} -> {0:1, 1:1, 3:1, 6:1} -> {0:1, 1:1, 3:1, 6:1, 10:1}
We check if (current_sum - k) exists in map to find subarray.

Dry Run Walkthrough

Input: array: [1, 2, 3], k = 3

Goal: Find how many continuous subarrays sum to 3

Step 1: Initialize map with {0:1} and sum = 0

map = {0:1}, sum = 0

Why: We start with sum 0 counted once to handle subarrays starting at index 0

Step 2: Add first element 1 to sum (sum=1), check if sum-k= -2 in map

sum=1, map={0:1}

Why: No subarray ending here sums to k because -2 not in map

Step 3: Add sum=1 to map: map={0:1,1:1}

map={0:1,1:1}

Why: Record sum 1 seen once

Step 4: Add second element 2 to sum (sum=3), check if sum-k=0 in map

sum=3, map={0:1,1:1}

Why: sum-k=0 is in map, so subarray ending here sums to k

Step 5: Increment count by map[0]=1, add sum=3 to map: map={0:1,1:1,3:1}

count=1, map={0:1,1:1,3:1}

Why: Found one subarray (from index 0 to 1) summing to k

Step 6: Add third element 3 to sum (sum=6), check if sum-k=3 in map

sum=6, map={0:1,1:1,3:1}

Why: sum-k=3 is in map, so subarray ending here sums to k

Step 7: Increment count by map[3]=1, add sum=6 to map: map={0:1,1:1,3:1,6:1}

count=2, map={0:1,1:1,3:1,6:1}

Why: Found second subarray (from index 2 to 2) summing to k

Result:

Final count = 2
Subarrays: [1,2] and [3]

Annotated Code

DSA Java

import java.util.HashMap;

public class SubarraySumEqualsK {
    public static int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // sum 0 seen once
        int count = 0;
        int sum = 0;
        for (int num : nums) {
            sum += num; // add current number to sum
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k); // add count of previous sums that match
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1); // record current sum
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int k = 3;
        int result = subarraySum(nums, k);
        System.out.println(result);
    }
}

map.put(0, 1); // sum 0 seen once

Initialize map with sum 0 to handle subarrays starting at index 0

sum += num; // add current number to sum

Accumulate running sum of elements

if (map.containsKey(sum - k)) {

Check if a previous sum exists that forms subarray summing to k

count += map.get(sum - k); // add count of previous sums that match

Increment count by number of times (sum-k) appeared

map.put(sum, map.getOrDefault(sum, 0) + 1); // record current sum

Record current sum frequency for future matches

Output

2

Complexity Analysis

Time: O(n) because we traverse the array once and do constant time map operations per element

Space: O(n) because in worst case all prefix sums are unique and stored in the map

vs Alternative: Naive approach is O(n^2) by checking all subarrays sums; this method uses a map to reduce to O(n)

Edge Cases

Empty array

Returns 0 as no subarrays exist

DSA Java

map.put(0, 1); // sum 0 seen once

Array with all zeros and k=0

Counts all subarrays of zeros correctly using map frequencies

DSA Java

count += map.get(sum - k); // add count of previous sums that match

No subarray sums to k

Returns 0 as count remains zero

DSA Java

if (map.containsKey(sum - k)) {

When to Use This Pattern

When asked to find count of continuous subarrays summing to a target, use prefix sums with a hash map to track sums and find matches efficiently.

Common Mistakes

Mistake: Not initializing map with sum 0 count 1, missing subarrays starting at index 0
Fix: Add map.put(0, 1) before loop to handle subarrays from start

Mistake: Updating count before checking if (sum-k) exists in map
Fix: Check map.containsKey(sum-k) before adding to count

Mistake: Not updating map with current sum frequency
Fix: Use map.put(sum, map.getOrDefault(sum, 0) + 1) to record sums

Summary

Counts how many continuous subarrays sum to a target value k using prefix sums and a hash map.

Use when you need to find subarrays with a specific sum efficiently in linear time.

The key insight is that difference of prefix sums reveals subarray sums, and storing counts in a map lets you find matches quickly.

Practice

1. What is the main purpose of using a hash map in the Subarray Sum Equals K problem?

easy

A. To store cumulative sums and their frequencies for quick lookup

B. To sort the array elements before processing

C. To store the original array elements as keys

D. To keep track of the maximum subarray length

Solution

1. Step 1: Understand the problem requirement

   The problem requires finding the number of continuous subarrays whose sum equals a target value k.

2. Step 2: Role of hash map in solution

   The hash map stores cumulative sums encountered so far and their counts, allowing quick checks if a subarray sum equals k by checking if (current_sum - k) exists.

3. Final Answer:

   To store cumulative sums and their frequencies for quick lookup -> Option A

4. Quick Check:

   Hash map stores sums for fast subarray sum checks [OK]

Hint: Hash map tracks sums to find subarrays fast [OK]

Common Mistakes:

• Thinking hash map stores array elements as keys
• Assuming sorting is needed
• Using hash map to track max length instead of counts

2. Which of the following Java code snippets correctly initializes the hash map used to store cumulative sums and their counts?

easy

A. HashMap map = new HashMap();"

B. HashMap map = new HashMap<>();

C. HashMap map = new HashMap<>();

D. HashMap map = new HashMap<Integer>();

Solution

1. Step 1: Check Java generics syntax

   Java requires wrapper classes like Integer for generics, and diamond operator <> is used for type inference.

2. Step 2: Identify correct initialization

   HashMap map = new HashMap<>(); uses HashMap map = new HashMap<>(); which is correct and modern syntax.

3. Final Answer:

   HashMap map = new HashMap<>(); -> Option C

4. Quick Check:

   Use wrapper classes and diamond operator for HashMap [OK]

Hint: Use Integer, not int, and diamond operator <> [OK]

Common Mistakes:

• Using primitive types int in generics
• Missing diamond operator <>
• Incorrect constructor syntax

3. What is the output of the following Java code snippet?

int[] nums = {1, 2, 3};
int k = 3;
int count = 0;
HashMap map = new HashMap<>();
map.put(0, 1);
int sum = 0;
for (int num : nums) {
    sum += num;
    if (map.containsKey(sum - k)) {
        count += map.get(sum - k);
    }
    map.put(sum, map.getOrDefault(sum, 0) + 1);
}
System.out.println(count);

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Calculate cumulative sums and check subarrays

   nums = [1,2,3], k=3 - sum=1, map has 0:1, sum-k=1-3=-2 not in map - sum=3, sum-k=0 in map with count 1, count=1 - sum=6, sum-k=3 in map with count 1, count=2

2. Step 2: Final count of subarrays with sum k

   Two subarrays sum to 3: [1,2] and [3].

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Two subarrays sum to k=3 [OK]

Hint: Track sums and check (sum-k) in map to count subarrays [OK]

Common Mistakes:

• Not initializing map with (0,1)
• Forgetting to update count correctly
• Misunderstanding cumulative sum logic

4. Identify the error in the following Java code snippet for counting subarrays with sum k:

int[] nums = {1, -1, 0};
int k = 0;
int count = 0;
HashMap map = new HashMap<>();
int sum = 0;
for (int num : nums) {
    sum += num;
    if (map.containsKey(sum - k)) {
        count += map.get(sum - k);
    }
    map.put(sum, 1);
}
System.out.println(count);

medium

A. Incorrect array declaration syntax

B. Using sum - k instead of sum + k in map lookup

C. Not updating sum inside the loop

D. Missing initialization of map with (0,1)

Solution

1. Step 1: Check map initialization

   The map should start with (0,1) to count subarrays starting at index 0. This is missing here.

2. Step 2: Check map update logic

   Also, map.put(sum, 1) overwrites counts instead of incrementing. But the main error is missing initial (0,1).

3. Final Answer:

   Missing initialization of map with (0,1) -> Option D

4. Quick Check:

   Initialize map with (0,1) to count empty prefix sum [OK]

Hint: Always start map with (0,1) before loop [OK]

Common Mistakes:

• Not initializing map with (0,1)
• Overwriting counts instead of incrementing
• Confusing sum-k with sum+k

5. Given an array nums = {3, 4, 7, 2, -3, 1, 4, 2} and k = 7, how many continuous subarrays sum to k? Use the hash map approach to find the answer.

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Calculate cumulative sums and track counts

   Initialize map with (0,1), sum=0, count=0 Iterate nums: - sum=3, sum-k=-4 not in map, map[3]=1 - sum=7, sum-k=0 in map(1), count=1, map[7]=1 - sum=14, sum-k=7 in map(1), count=2, map[14]=1 - sum=16, sum-k=9 not in map, map[16]=1 - sum=13, sum-k=6 not in map, map[13]=1 - sum=14, sum-k=7 in map(1), count=3, map[14]=2 - sum=18, sum-k=11 not in map, map[18]=1 - sum=20, sum-k=13 in map(1), count=4, map[20]=1

2. Step 2: Identify subarrays

   Four subarrays sum to 7: [3,4], [7], [7,2,-3,1], [1,4,2].

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count subarrays with sum k using cumulative sums [OK]

Hint: Count subarrays by checking (sum-k) in map during iteration [OK]

Common Mistakes:

• Missing subarrays with negative numbers
• Not updating counts correctly when sum repeats
• Forgetting to initialize map with (0,1)