LeetCode Solutions Blog

Subarray Sum Equals K

Number: 560

Difficulty: Medium

Paid? No

Problem Description

Given an array of integers nums and an integer k, return the total number of contiguous non-empty subarrays whose sum equals k.

Key Insights

Utilize the prefix sum technique to simplify sum calculation for subarrays.
Use a hash table (or dictionary/map) to store the frequency of prefix sums encountered.
For each element, check if (current prefix sum - k) exists in the hash table; if it does, it indicates a valid subarray.
Initialize the hash table with {0: 1} to manage cases where a subarray’s sum is exactly k.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We solve the problem by maintaining a running sum (prefix sum) and using a hash table to record the number of times each sum has occurred. As we iterate through the array, we update the running sum. For each new sum, we check if (current sum - k) exists in our hash table. If it does, the value associated with (current sum - k) gives the number of subarrays ending at the current index that sum to k. This method efficiently computes the result in a single pass through the array.

Code Solutions

# Function to calculate the number of subarrays that sum to k
def subarraySum(nums, k):
    # Dictionary to store frequency of prefix sums
    prefix_counts = {0: 1}  # Initialize with prefix sum 0
    current_sum = 0  # Running sum initialization
    count = 0  # To count the valid subarrays
    # Iterate over the array
    for num in nums:
        current_sum += num  # Update the running (prefix) sum
        # Check if there's a prefix sum that differs from current_sum by k
        count += prefix_counts.get(current_sum - k, 0)
        # Update the frequency count for the current sum
        prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
    return count

# Example usage:
print(subarraySum([1,1,1], 2))  # Expected output: 2