Subarray Sum Equals K

Problem:

Given an integer array nums, find the total number of continuous subarrays whose sum equals k.

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of k is [-1e7, 1e7].

Example:

Input: nums = [1, 1, 1], k = 2 Output: 2 Explanation: The subarrays with sum equal to 2 are [1, 1] and [1, 1].

Approach:

To solve this problem, we can use a hashmap to store the cumulative sums and their frequencies. We iterate over the array and keep track of the cumulative sum at each element. For each cumulative sum encountered, we check if the difference between the current cumulative sum and k exists in the hashmap. If it exists, it means that there is a subarray with sum equal to k. We increment our count by the frequency of the difference.

Algorithm:

1. Initialize a hashmap cumulativeSumFreq to store the cumulative sums and their frequencies. Also, initialize count and cumulativeSum to 0.
2. Iterate over the input array nums:
   1. Increment cumulativeSum by the current element.
   2. If cumulativeSum is equal to k, increment count by 1.
   3. If cumulativeSum - k exists in cumulativeSumFreq, increment count by the frequency of cumulativeSum - k.
   4. Increment the frequency of cumulativeSum in cumulativeSumFreq by 1.
3. Return the count as the total number of subarrays with sum equal to k.

Complexity Analysis:

The time complexity for this approach is O(n), where n is the length of the input array nums. This is because we iterate over the array only once.

The space complexity is O(n) as well, due to the usage of the hashmap cumulativeSumFreq. In the worst case, all elements in nums could be distinct and have unique cumulative sums, resulting in the hashmap having a space of O(n).

Code Implementation in Python:

def subarraySum(nums, k):
    cumulativeSumFreq = {0: 1}  # Initialize with (sum = 0, freq = 1)
    count, cumulativeSum = 0, 0
    
    for num in nums:
        cumulativeSum += num
        if cumulativeSum == k:
            count += 1
        
        if cumulativeSum - k in cumulativeSumFreq:
            count += cumulativeSumFreq[cumulativeSum - k]
        
        cumulativeSumFreq[cumulativeSum] = cumulativeSumFreq.get(cumulativeSum, 0) + 1
    
    return count

Test the Solution:

Let's test our solution with the example provided in the problem statement.

assert subarraySum([1, 1, 1], 2) == 2

Since there are two subarrays with sum equal to 2 ([1, 1] and [1, 1]), the output should be 2, which matches the expected result.