Subarray Sum Equals K

Master this topic with zero to advance depth.

Subarray Sum Equals K

The sum of subarray nums[i...j] is PrefixSum[j] - PrefixSum[i-1]. If this difference equals k, then PrefixSum[j] - k = PrefixSum[i-1]. We use a HashMap to count occurrences of PrefixSum[i-1].

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.

Visual Representation

nums = [1, 2, 3], k = 3

Subarrays:
[1, 2] -> Sum = 3 (Valid)
[3]    -> Sum = 3 (Valid)

Answer: 2

Medium

Examples

Input: nums = [1,1,1], k = 2
Output: 2
The subarrays [1,1] and [1,1] have sum 2.

Input: nums = [1,2,3], k = 3
Output: 2
The subarrays [1,2] and [3] have sum 3.

Approach 1

Level I: Brute Force (All Subarrays)

Intuition

We check every possible subarray by iterating through all pairs of start indices i and end indices j. For each pair, we calculate the sum of elements from i to j. If the sum equals k, we increment our count.

⏱ O(N²) after optimizing the inner sum loop.💾 O(1) extra space.

Detailed Dry Run

i	j	Subarray	Sum	Count
0	0	[1]	1	0
0	1	[1, 1]	2	1 (k=2)
1	1	[1]	1	1
1	2	[1, 1]	2	2 (k=2)

java

import java.util.*;

public class Main {
    public static int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) count++;
            }
        }
        return count;
    }

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

Approach 2

Level II: Better Solution (Cumulative Sum O(N²))

Avoid the inner sum loop by adding nums[j] to the current running sum as you expand the subarray.

⏱ O(N²)💾 O(1)

Detailed Dry Run

j	Running Sum	k=2?
0	1	No
1	2	Yes
2	3	No

java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

Approach 3

Level III: Optimal Solution (Prefix Sum + HashMap)

Intuition

The sum of subarray nums[i...j] is PrefixSum[j] - PrefixSum[i-1]. If this difference equals k, then PrefixSum[j] - k = PrefixSum[i-1]. We use a HashMap to store the frequencies of prefix sums encountered so far. For each new PrefixSum[j], we check how many times PrefixSum[j] - k has appeared before.

⏱ O(N) single pass traversal.💾 O(N) to store prefix sums in the map.

Detailed Dry Run

Prefix Sum Visual

nums = [1, 2, 3], k = 3 Initial Map: {0: 1} (Subarray with sum 0 starts from beginning)

Index	Num	Current Prefix Sum (S)	Target (S - k)	Found in Map?	New Map State	Count
0	1	1	-2	No	`{0:1, 1:1}`	0
1	2	3	0	Yes (freq 1)	`{0:1, 1:1, 3:1}`	1
2	3	6	3	Yes (freq 1)	`{0:1, 1:1, 3:1, 6:1}`	2

java

import java.util.*;

public class Main {
    public static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int count = 0, sum = 0;
        for (int n : nums) {
            sum += n;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

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

← Previous QuestionTop K Frequent Elements

Next Question →Find All Duplicates in an Array

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.