Subarray Sum Equals K

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

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;
    }
}