Course4all

Subarray Sum Equals K

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

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

ijSubarraySumCount
00[1]10
01[1, 1]21 (k=2)
11[1]11
12[1, 1]22 (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

ijRunning Sumk=2?
001No
012Yes
023No
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)
IndexNumCurrent Prefix Sum (S)Target (S - k)Found in Map?New Map StateCount
011-2No{0:1, 1:1}0
1230Yes (freq 1){0:1, 1:1, 3:1}1
2363Yes (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));
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionTop K Frequent Elements
Next Question →Find All Duplicates in an Array