Subarray Sum Equals K

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.

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: Prefix Sum with Hash Map (Optimal Solution)

Algorithm

1. Compute the running (prefix) sum while iterating through the array
2. If currentSum - k was seen earlier as a prefix sum, then the subarray between those two points sums to k; add the recorded count to the answer
3. Record/update the frequency of the current prefix sum in the hash map
4. Initialize the map with {0: 1} to handle subarrays that start from index 0

Time & Space Complexity

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(n) - hash map stores prefix sum frequencies

Java Implementation

import java.util.HashMap;
import java.util.Map;

public class SubarraySumEqualsK {

    /**
     * Count the total number of subarrays whose sum equals k.
     * @param nums Array of integers
     * @param k Target sum
     * @return Number of subarrays summing to k
     */
    public static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);

        int currentSum = 0;
        int count = 0;

        for (int num : nums) {
            currentSum += num;

            // If there is a prefix sum of (currentSum - k),
            // the subarray between them sums to k
            count += prefixSumCount.getOrDefault(currentSum - k, 0);

            prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }

        return count;
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        int[] nums1 = {1, 1, 1};
        int k1 = 2;
        System.out.println("Input: nums = [1, 1, 1], k = 2");
        System.out.println("Output: " + subarraySum(nums1, k1)); // Expected: 2

        // Test case 2
        int[] nums2 = {1, 2, 3};
        int k2 = 3;
        System.out.println("Input: nums = [1, 2, 3], k = 3");
        System.out.println("Output: " + subarraySum(nums2, k2)); // Expected: 2
    }
}

Example Walkthrough

For nums = [1, 1, 1] and k = 2:

1. Map starts as {0: 1}
2. num=1: currentSum=1. Look for 1-2=-1 (not found). Map: {0: 1, 1: 1}
3. num=1: currentSum=2. Look for 2-2=0 (found 1 time). count=1. Map: {0: 1, 1: 1, 2: 1}
4. num=1: currentSum=3. Look for 3-2=1 (found 1 time). count=2. Map: {0: 1, 1: 1, 2: 1, 3: 1}

Subarrays: [1, 1] (indices 0-1) and [1, 1] (indices 1-2). Final answer: 2.

Key Points

1. Prefix Sum Trick: Sum of subarray (i, j] = prefix[j] - prefix[i]
2. Lookup by Difference: A subarray summing to k exists whenever currentSum - k was a previous prefix sum
3. Zero Initialization: Seed the map with {0: 1} so subarrays starting at index 0 are counted
4. Handles Negatives: Unlike the two-pointer or sliding-window approaches, the hash map method works with negative numbers
5. O(n) Runtime: Each element is processed exactly once