Subarray Sum Equals K

December 26, 2023

Problem #

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

Solution #

To solve the problem of finding the total number of continuous subarrays whose sum equals a given integer k, a common and efficient approach is to use a cumulative sum combined with a hash table. This method allows us to efficiently track the sum of subarrays and check for the existence of the required sum. Here’s a Python implementation for the problem:

def subarraySum(nums, k):
    count = 0
    current_sum = 0
    prefix_sum = {0: 1}  # Initialize with sum 0 occurring once

    for num in nums:
        current_sum += num
        # Check if there is a prefix sum that, if removed, leads to sum k
        if current_sum - k in prefix_sum:
            count += prefix_sum[current_sum - k]

        # Record the current sum's occurrence
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1

    return count

# Example Usage
nums = [1, 1, 1]
k = 2
print("Number of subarrays:", subarraySum(nums, k))

In this code:

• We keep a running sum (current_sum) of the elements as we iterate through the array.
• We use a hash table (prefix_sum) to store the number of times a particular cumulative sum has occurred.
• For each element, we check if current_sum - k exists in the hash table. If it does, it means there is a subarray that sums to k, and we add the count of such occurrences to count.
• We then update the hash table with the current cumulative sum.

The idea behind this algorithm is that if the cumulative sum up to two indices, say i and j, is the same, the sum of the elements lying between i and j is 0. Extending this idea, if current_sum - k has already been seen, it means there is a subarray ending at the current index which sums to k.

This algorithm has a time complexity of O(n), where n is the number of elements in the array, since it involves a single pass through the array.