Problem Statement

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

A subarray is a contiguous non-empty sequence of elements within an array.

Additional information

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

Example 1:

Input: nums = [1,1,1], k = 2

Output: 2

Explanation: The subarrays [1,1] (indices 0 to 1) and [1,1] (indices 1 to 2) both sum to 2.

Example 2:

Input: nums = [1,2,3], k = 3

Output: 2

Explanation: The subarrays [1,2] and [3] both sum to 3.

Brute Force (Nested Loops)

Intuition

The most straightforward way to find all subarrays that sum to k is to literally calculate the sum of every possible subarray in existence and count how many match our target.

We can use a nested loop: the outer loop sets the starting index i, and the inner loop sets the ending index j. As we expand j, we keep a running total of the current subarray. Every time that running total exactly equals k, we increment a counter.

Algorithm

1. Initialize a count variable to 0.
2. Iterate i from 0 to the length of nums. This is the start of the subarray.
3. Initialize current_sum = 0.
4. Iterate j from i to the length of nums. This expands the subarray to the right.
5. Add nums[j] to current_sum.
6. If current_sum == k, increment the count.
7. Return count after checking all combinations.

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    n = len(nums)
    
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]
            
            if current_sum == k:
                count += 1
                
    return count

Time & Space Complexity

• Time complexity: O(N^2)
  • Reason: We use a nested loop to evaluate the sum of every possible contiguous subarray. With an array length of up to 20,000 elements, this quadratic time complexity will cause a Time Limit Exceeded (TLE) error.
• Space complexity: O(1)
  • Reason: We only use a couple of integer variables (count and current_sum) to track our state.

Prefix Sum with Hash Map - Optimal

Intuition

We can optimize this to a single O(N) pass using a running "prefix sum" and a little bit of algebra.

Imagine we are walking through the array and keeping a running total of all elements up to our current index. Let's call this prefix_sum.
If we want to know if a valid subarray ending at our current index exists, we are essentially asking: "Did we ever see a previous prefix sum that, when subtracted from our current prefix sum, leaves exactly k?"

Algebraically: current_prefix_sum - previous_prefix_sum = k
Rearranged: previous_prefix_sum = current_prefix_sum - k

So, at every step, we calculate current_prefix_sum - k. If that number exists in our history of previous prefix sums, we have found a valid subarray! We can use a Hash Map to store the frequencies of every prefix sum we encounter to instantly look up this history.

Algorithm

1. Initialize count = 0 and prefix_sum = 0.
2. Initialize a Hash Map prefix_map with {0: 1}.
   • Crucial Note: We seed the map with 0 occurring 1 time. This handles the edge case where a prefix sum exactly equals k right from the very beginning of the array (meaning prefix_sum - k = 0).
3. Iterate through each num in nums:
   • Add num to prefix_sum.
   • Calculate the target history value: diff = prefix_sum - k.
   • If diff exists in prefix_map, it means we can chop off a previous prefix to leave exactly k. Add the frequency of diff to count.
   • Finally, record the current prefix_sum into the prefix_map by incrementing its frequency (or setting it to 1 if it's new).
4. Return count.

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix_sum = 0
    
    # Base case: a prefix sum of 0 has been seen exactly 1 time
    prefix_map = {0: 1}
    
    for num in nums:
        prefix_sum += num
        
        # Check if we can chop off a previous prefix to get exactly k
        diff = prefix_sum - k
        if diff in prefix_map:
            count += prefix_map[diff]
            
        # Record the current prefix sum in our history
        prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
        
    return count

Time & Space Complexity

• Time complexity: O(N)
  • Reason: We iterate through the nums array exactly once. Hash Map lookups and insertions operate in O(1) constant time.
• Space complexity: O(N)
  • Reason: In the worst-case scenario, every prefix sum we calculate is completely unique, meaning we will store N key-value pairs in our prefix_map.