Subarray Sum Equals K medium

Problem Statement

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

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

Explanation: The subarrays are [1,1] and [1,1].

Example 2:

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

Explanation: The subarrays are [3] and [1,2].

Steps and Explanation

This problem can be efficiently solved using a hash map to store the cumulative sum and its frequency. We iterate through the array, calculating the cumulative sum at each point. For each cumulative sum, we check if cumulativeSum - k exists in the hash map. If it does, it means there's a subarray ending at the current index with a sum equal to k. The frequency of cumulativeSum - k represents the number of such subarrays.

1. Initialization: Create a hash map sumMap to store cumulative sums and their frequencies. Initialize count to 0 (to store the total number of subarrays). Initialize cumulativeSum to 0.

2. Iteration: Iterate through the nums array.

3. Cumulative Sum Update: For each element num, update cumulativeSum by adding num to it.

4. Check for Subarray:

   • If cumulativeSum == k, it means a subarray from the beginning to the current index has a sum of k. Increment count.
   • Check if cumulativeSum - k is present in sumMap. If it is, it means there's a subarray ending at the current index with a sum of k. Add the frequency of cumulativeSum - k to count.

5. Update HashMap: Add cumulativeSum to sumMap. If cumulativeSum already exists, increment its frequency. We initialize the frequency of 0 to 1, because a subarray starting from index 0 always exists.

6. Return Count: After iterating through the entire array, return count.

Code (Java)

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

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> sumMap = new HashMap<>();
        sumMap.put(0, 1); //Important: Handle subarrays starting from index 0
        int cumulativeSum = 0;
        int count = 0;

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

        return count;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. HashMap operations (get and put) take O(1) on average.

• Space Complexity: O(n) in the worst case, as the hash map could store up to n distinct cumulative sums. In the best case, it could be O(1).