Optimal Python Solution for Subarray Sum Equals K (Interview Script)

2025-10-05

The Logic

• A brute force approach checks all subarrays and is too slow.
• Prefix sums allow us to track cumulative sums efficiently.
• A hash map stores how often each prefix sum has appeared.

Implementation / Diagram

Key Invariant

If current_sum minus k has appeared before, a valid subarray ending at this index exists.

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    seen = {0: 1}

    for num in nums:
        prefix_sum += num
        if prefix_sum - k in seen:
            count += seen[prefix_sum - k]
        seen[prefix_sum] = seen.get(prefix_sum, 0) + 1

    return count