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

1. Prefix Sum: We'll use a prefixSum map to store the cumulative sum of elements encountered so far and their frequency. The key is the cumulative sum, and the value is the count of times that sum has appeared. We initialize the map with a 0 sum having a count of 1 because an empty subarray (before we've even started) has a sum of 0.

2. Iteration: We iterate through the nums array. In each iteration, we calculate the current cumulative sum (currentSum).

3. Check for k: We check if currentSum - k exists as a key in the prefixSum map. If it does, it means there was a previous subarray whose sum was currentSum - k. Adding the current element to this previous subarray will result in a subarray with a sum of k. We add the frequency of currentSum - k to our count of subarrays.

4. Update Prefix Sum: We update the prefixSum map by incrementing the count for the currentSum.

5. Return Count: Finally, we return the count of subarrays that sum to k.

Explanation

The core idea is to efficiently find subarrays that sum to k. Instead of checking every possible subarray (which would be O(n^2)), we leverage the prefix sum technique. By keeping track of cumulative sums and their frequencies, we can quickly determine if a subarray with the desired sum exists by checking if currentSum - k is present in the prefixSum map. This drastically reduces the time complexity.

Code

function subarraySum(nums: number[], k: number): number {
    const prefixSum = new Map<number, number>();
    prefixSum.set(0, 1); // Initialize for empty subarray
    let currentSum = 0;
    let count = 0;

    for (const num of nums) {
        currentSum += num;
        if (prefixSum.has(currentSum - k)) {
            count += prefixSum.get(currentSum - k)!;
        }
        prefixSum.set(currentSum, (prefixSum.get(currentSum) || 0) + 1);
    }

    return count;
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. Map operations (get and set) are typically O(1) on average.

• Space Complexity: O(n) in the worst case. The prefixSum map could potentially store up to n distinct cumulative sums. In the best case (many repeated sums), it could be much smaller.