Subarray Sum Equals K - Java Solution

1. Introduction

This blog post addresses the "Subarray Sum Equals K" problem, a common challenge in the realm of array manipulation and prefix sums. The task involves counting the number of contiguous subarrays in a given array whose sum equals a target value k. This problem is a classic example in computer science for understanding cumulative sums and hash maps.

Problem

Given an array of integers nums and an integer k, the objective is to return the total number of contiguous non-empty subarrays whose sum equals k.

Examples:

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

Output: 2

2. Input: nums = [1,2,3], k = 3

Output: 2

2. Solution Steps

1. Utilize a hash map to store the cumulative sum up to each index and its frequency.

2. Iterate through the array, calculating the cumulative sum.

3. For each cumulative sum, check how many times (if any) the sum cumulativeSum - k has occurred before, as this indicates a subarray summing to k.

4. Update the count of subarrays accordingly.

5. Update the hash map with the current cumulative sum.

6. Return the total count of such subarrays after completing the iteration.

3. Code Program

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

public class SubarraySumEqualsK {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1};
        int k = 2;
        System.out.println(subarraySum(nums, k)); // Test the function
    }

    // Function to find the total number of subarrays whose sum equals k
    public static int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // Initialize for the case when sum equals k

        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return count;
    }
}

Output:

2

Explanation:

1. subarraySum: This function counts the number of subarrays in nums whose sum equals k.

2. It uses a hash map map to store the cumulative sums and their frequencies.

3. As the function iterates through the array, it updates the cumulative sum sum and checks if sum - k is present in the map. If it is, it adds the frequency of sum - k to count.

4. The existence of sum - k in the map means there are previous subarrays which, when added to the current element, equal k.

5. The function updates the map with the current sum and its frequency.

6. After iterating through the array, count holds the total number of subarrays summing to k.

7. This approach efficiently calculates the desired count using the concept of prefix sums and hashing, ensuring a linear time complexity.