DATA STRUCTURES • ALGORITHMS

Subarray Sum Equals K

Given an array of integers, find the total number of continuous subarrays whose sum equals to K.

Time

O(N)

Space

O(N)

Key Principle 1

Prefix sum approach

Key Principle 2

Map stores count of previous prefix sums

Key Principle 3

Current sum - K must have been seen before

Key Principle 4

Handles negative numbers correctly

SUBARRAY_SUM_K_LAB
Current Step
Find total subarrays with sum K=3. Initialize sum=0 and map={0:1}.
Global Count
0
Playback
Prefix Sum Map ⠿
SUMCOUNT
01
Map Logic ⠿
1int count = 0, sum = 0;
2Map<Integer, Integer> map = new HashMap<>();
3map.put(0, 1);
4for (int i = 0; i < nums.length; i++) {
5    sum += nums[i];
6    if (map.containsKey(sum - k))
7        count += map.get(sum - k);
8    map.put(sum, map.getOrDefault(sum, 0) + 1);
9}
10return count;
1
[0]
2
[1]
3
[2]
-2
[3]
1
[4]
4
[5]
Current Prefix Sum
0
Looking for 0 - 3 = -3 in Map

Loading Lab...