560. Subarray Sum Equals K

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Brute Force	Check all possible subarrays and calculate their sums.	\(O(n^2)\): Two nested loops	\(O(1)\): No extra space used
Prefix Sum + Hashmap	Use a hashmap to store prefix sums and their counts. Check for complement in each step.	\(O(n)\): Single iteration	\(O(n)\): Hashmap stores prefix sums

Implementation

PythonJavaScriptGo

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # key:value = prefix_sum: count
        prefix_sums = {0: 1}
        counts = 0

        curr_sum = 0
        for i, num in enumerate(nums):
            curr_sum += num
            complement = curr_sum - k
            # Add up 
            if complement in prefix_sums:
                counts += prefix_sums[complement]
            # Update prefix_sums
            if curr_sum in prefix_sums:
                prefix_sums[curr_sum] += 1
            else:
                prefix_sums[curr_sum] = 1
        return counts

```