Problem Statement

You are given an integer array nums and an integer k.
Your task is to find the total number of continuous subarrays whose sum equals k.

Example

Input: nums = [1, 1, 1], k = 2  
Output: 2

There are two subarrays that sum up to 2: [1,1] (from index 0 to 1) and [1,1] (from index 1 to 2).

1. Understanding the Problem

A subarray is a continuous part of the array, meaning elements are taken together without skipping any index.

For each possible subarray, if the sum of its elements equals k, we count it.

If we try to calculate the sum of all possible subarrays directly using two nested loops, it works but is slow for large inputs — time complexity will be O(n²).

We can do better using a prefix sum and hashmap.

2. Brute Force Approach

Idea:
For each element, calculate the sum of every subarray starting from it and count those that equal k.

Java Code (Brute Force):

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

Explanation:

1. The outer loop picks a starting point.
2. The inner loop adds numbers from that start to the end.
3. Whenever the running sum equals k, we increase our count.

Time Complexity: O(n²)
Space Complexity: O(1)

This method works but is inefficient for large arrays.

3. Optimized Approach Using Prefix Sum and HashMap

Concept of Prefix Sum:

• The prefix sum at index i is the sum of all elements from the beginning up to index i.
• For any subarray nums[i..j], the sum can be written as: sum(i..j) = prefixSum[j] - prefixSum[i - 1] If sum(i..j) should equal k, then: prefixSum[j] - prefixSum[i - 1] = k → prefixSum[i - 1] = prefixSum[j] - k

This means:

• For every current prefix sum, if there is a previous prefix sum equal to (currentSum - k), then the subarray between those indices sums to k.

We use a HashMap to store how many times each prefix sum has appeared.

4. Steps for the Optimized Solution

1. Initialize a map to store prefix sums and their frequency.
2. Add an entry (0, 1) to the map, because a prefix sum of 0 exists before starting.
3. Iterate through the array:
   • Add the current number to currentSum.
   • Check if (currentSum - k) exists in the map.
     If it does, it means there is a subarray ending here whose sum is k.
   • Add map.get(currentSum - k) to the count.
   • Update the frequency of currentSum in the map.
4. Return the total count.

5. Java Code (Optimized O(n) Solution)

import java.util.HashMap;

public class SubarraySumEqualsK {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0, 1);
        
        int currentSum = 0;
        int count = 0;
        
        for (int num : nums) {
            currentSum += num;
            
            if (prefixSumMap.containsKey(currentSum - k)) {
                count += prefixSumMap.get(currentSum - k);
            }
            
            prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);
        }
        
        return count;
    }
}

6. Step-by-Step Example

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

Step	num	currentSum	currentSum – k	Found in map?	Count	Map after update
1	1	1	-2	No	0	{0=1, 1=1}
2	2	3	0	Yes	1	{0=1, 1=1, 3=1}
3	3	6	3	Yes	2	{0=1, 1=1, 3=1, 6=1}

Total subarrays = 2 → [1,2] and [3].

7. Complexity Analysis

Time Complexity: O(n)
We traverse the array once, and each lookup in the map is O(1).

Space Complexity: O(n)
We store prefix sums in the map.

8. Summary

• Brute Force approach is easy to understand but slow (O(n²)).
• Optimized approach uses prefix sum and HashMap for an efficient O(n) solution.
• This method is a powerful pattern for subarray problems involving sums or differences.