Subarray Sum Equals K

Updated on 04 July, 2025
Subarray Sum Equals K header image

Problem Statement

In this problem, you are presented with an array of integers, nums, and a single integer, k. Your task is to determine the number of subarrays within nums that sum up to k. A "subarray" is defined as a contiguous, non-empty portion of the original array. Thus, each subarray represents a sequential subset of the elements from nums.

Examples

Example 1

Input:

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

Output:

2

Example 2

Input:

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

Output:

2

Constraints

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

Approach and Intuition

To solve the problem of finding the number of subarrays that sum up to k, we can explore several approaches. Here's a step-by-step breakdown of a feasible method using a hashmap to track the cumulative sums:

  1. Initialize a hashmap (or dictionary in Python) to store the cumulative sums encountered so far. The key will be the sum, and the value will be how frequently this sum appears.

  2. Initialize the hashmap with the key 0 set to 1. This accounts for a subarray that might begin from the first element and sum to k.

  3. Initialize a variable, current_sum, to zero. This will keep the cumulative total as we iterate through the list.

  4. Initialize a variable, count, to zero. This will count the number of times we find a subarray that sums to k.

  5. Iterate through each element in nums. For each element:

    • Add it to current_sum.
    • Calculate the difference between the current_sum and k. This difference tells us the sum we need to have seen before in the current_sum sequence to form a subarray totaling to k at the current element.
    • If this difference exists in the hashmap, it means that there were some prior subarrays that sum to this difference. The number of such arrays gives the number of times a k-sum subarray ends at the current location.
    • Increment the count by how many times the needed sum (difference calculated earlier) has been seen.
    • Update the hashmap with the new current_sum. If current_sum has already been seen, increment its value to indicate it's happened again; otherwise, add it to the hashmap.

This approach efficiently counts the required subarrays with the desired sum by leveraging the cumulative sum technique and hashmap storage. The key insight is recognizing that the condition current_sum - k existing in our cumulative sum records indicates that a valid subarray (or subarrays) can be formed ending at the current index. This method provides a linear time complexity relative to the array's length, making it suitable for even larger datasets within the provided constraints.

Solutions

  • Java
java
public class Solution {
    public int countSubarraysWithSum(int[] array, int target) {
        int total = 0, cumulativeSum = 0;
        HashMap<Integer, Integer> prefixSums = new HashMap<>();
        prefixSums.put(0, 1);
        for (int j = 0; j < array.length; j++) {
            cumulativeSum += array[j];
            if (prefixSums.containsKey(cumulativeSum - target))
                total += prefixSums.get(cumulativeSum - target);
            prefixSums.put(cumulativeSum, prefixSums.getOrDefault(cumulativeSum, 0) + 1);
        }
        return total;
    }
}

The provided Java solution calculates how many subarrays within an array have a sum equal to a specified target value. Follow the approach below to understand the implementation details.

  • Initialize two integer variables: total to store the final count of subarrays and cumulativeSum to store the sum of elements as you iterate through the array.
  • Create a HashMap named prefixSums to store the cumulative sum up to each index as the key and the number of times this cumulative sum has occurred as the value. Start by putting the key-value pair (0, 1) in the map to handle cases where the subarray starts from index 0.

As you iterate through each element of the array:

  1. Add the current element to cumulativeSum.
  2. Check if (cumulativeSum - target) exists in the prefixSums map. If it does, the difference between the current cumulative sum and this key indicates a subarray sum that equals the target. Add the value of prefixSums.get(cumulativeSum - target) to total.
  3. Update prefixSums for the current cumulativeSum. If it doesn't exist, add it with a default count of 0 and then increment by 1.

At the end of the loop, the total variable contains the final count of subarrays whose sum equals the specified target. The use of a hashmap optimizes the search for the required sums, effectively reducing the computational overhead compared to a naive approach involving nested loops.

Comments

No comments yet.