I'm going to explain LeetCode Problem 560: Subarray Sum Equals K to you.

Problem Description

Given an integer array nums and an integer k, you need to find the number of contiguous subarrays whose sum equals k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Explanation: [1,1] and [1,1] (Note there are two subarrays at different positions)

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
Explanation: [1,2] and [3]

Step-by-Step Solution Approach

Step 1: Brute Force Solution (Understanding the Problem Essence)

The most straightforward approach is to enumerate all possible subarrays:

• For each starting position i, calculate the sum of subarrays from i to each ending position j
• Check if the sum equals k

def subarraySum(nums, k):
    count = 0
    n = len(nums)
    
    for i in range(n):          # Starting position
        current_sum = 0
        for j in range(i, n):   # Ending position
            current_sum += nums[j]
            if current_sum == k:
                count += 1
    
    return count

Time Complexity: O(n²) - For each starting position, we traverse to the end of the array
Space Complexity: O(1)

This method is intuitive but inefficient for large datasets.

Step 2: Optimization Idea - The Concept of Prefix Sum

We can introduce the concept of prefix sum to optimize:

• Define prefix[i] as the sum from nums[0] to nums[i]
• Then the sum of subarray [i, j] = prefix[j] - prefix[i-1]

Specifically:

• If we want the sum of subarray [i, j] to be k, then:
  prefix[j] - prefix[i-1] = k
• Transforming it: prefix[i-1] = prefix[j] - k

This means: For each position j, we need to find how many previous positions i satisfy prefix[i] = prefix[j] - k

Step 3: Hash Map Optimization

We can use a hash map to record the occurrence count of each prefix sum, allowing O(1) time queries:

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    prefix_count = {0: 1}  # Prefix sum 0 appears once (empty subarray)
    
    for num in nums:
        prefix_sum += num
        
        # Check if prefix[i] = prefix_sum - k exists
        if (prefix_sum - k) in prefix_count:
            count += prefix_count[prefix_sum - k]
        
        # Update the occurrence count of the current prefix sum
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
    
    return count

Step 4: Detailed Example Demonstration

Take nums = [1,1,1], k = 2 as an example:

Traversal Process:

1. i=0, num=1: prefix_sum=1

   • Need to find prefix_sum - k = 1-2 = -1, does not exist
   • prefix_count = {0:1, 1:1}

2. i=1, num=1: prefix_sum=2

   • Need to find 2-2=0, exists, count += prefix_count[0] = 1
   • prefix_count = {0:1, 1:1, 2:1}

3. i=2, num=1: prefix_sum=3

   • Need to find 3-2=1, exists, count += prefix_count[1] = 1
   • prefix_count = {0:1, 1:1, 2:1, 3:1}

Final result: count = 2

Step 5: Key Points Explanation

1. Why do we need prefix_count = {0: 1}?

   • This handles subarrays starting from the beginning of the array
   • For example, the sum of subarray [0, j] is prefix[j] - prefix[-1], and prefix[-1] should be 0

2. Why prefix_sum - k?

   • Because we are looking for: prefix[j] - prefix[i] = k
   • So prefix[i] = prefix[j] - k

3. Time Complexity: O(n) - Only one traversal of the array

4. Space Complexity: O(n) - Hash map stores prefix sums

Step 6: Considering Edge Cases

• Empty array: Return 0
• k=0: Requires special handling (but the algorithm naturally supports it)
• Contains negative numbers: Algorithm still works
• Multiple identical prefix sums: The hash map records counts, allowing correct statistics

This prefix sum + hash map method is the standard solution for "subarray sum equals k" type problems. Understanding this approach enables you to tackle similar problems with ease.