Subarray Sum Equals K - Python Solution

1. Introduction

"Subarray Sum Equals K" is an array processing problem that combines elements of cumulative sum and hash table techniques. It involves finding the number of contiguous subarrays within a given array that sum up to a specific value. This problem is a good exercise for understanding the use of cumulative sums to optimize subarray sum calculations and the role of hash tables in counting specific occurrences.

Problem

Given an array of integers nums and an integer k, the task is to return the total number of subarrays whose sum equals to k. A subarray is defined as a contiguous, non-empty sequence of elements within the array.

2. Solution Steps

1. Use a hash table to store the cumulative sum of elements up to the current index and its frequency.

2. Initialize a variable for the cumulative sum and another for the count of subarrays.

3. Iterate through the array, updating the cumulative sum at each step.

4. Check if cumulative_sum - k is in the hash table. If so, add its frequency to the count.

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

6. Continue this process for the entire array.

7. Return the count of subarrays whose sum equals k.

3. Code Program

def subarraySum(nums, k):
    count, cumulative_sum = 0, 0
    sum_freq = {0: 1}

    for num in nums:
        cumulative_sum += num
        count += sum_freq.get(cumulative_sum - k, 0)
        sum_freq[cumulative_sum] = sum_freq.get(cumulative_sum, 0) + 1

    return count

# Example Usage
print(subarraySum([1, 1, 1], 2))
print(subarraySum([1, 2, 3], 3))

Output:

2
2

Explanation:

1. Cumulative Sum Tracking: The function keeps track of the cumulative sum of elements encountered so far.

2. Hash Table Usage: A hash table (sum_freq) is used to store the frequency of each cumulative sum.

3. Subarray Counting: For each element, the function checks if cumulative_sum - k is in the hash table and adds the frequency to the count.

4. Updating Frequency: The frequency of the current cumulative sum in the hash table is updated.

5. Efficient Calculation: This approach allows for calculating the number of subarrays in linear time.

6. Result: The function returns the total number of subarrays that sum up to k.