LeetCode 560: Subarray Sum Equals K Solution in Python – A Step-by-Step Guide

Imagine you’re given a list of numbers—like [1, 1, 1]—and a target sum, say 2, and your task is to count how many continuous chunks of those numbers add up to that target, such as finding 2 subarrays ([1, 1] twice) that hit the mark. That’s the engaging challenge of LeetCode 560: Subarray Sum Equals K, a medium-level problem that’s a fantastic way to practice array manipulation in Python. We’ll explore two solutions: the Best Solution, a hash map with prefix sums that’s efficient and clever, and an Alternative Solution, a brute-force nested loop approach that’s straightforward but slower. With detailed examples, clear code, and a friendly tone—especially for the hash map method—this guide will help you tally those subarrays, whether you’re new to coding or leveling up. Let’s sum those chunks and start counting!

What Is LeetCode 560: Subarray Sum Equals K?

In LeetCode 560: Subarray Sum Equals K, you’re given an integer array nums and an integer k, and your task is to return the number of contiguous subarrays (subsequences of consecutive elements) whose sum equals k. For example, with nums = [1, 1, 1] and k = 2, there are 2 subarrays ([1, 1] starting at index 0 and 1) that sum to 2. This problem builds on LeetCode 1: Two Sum for sum-finding techniques but extends to contiguous subarrays of any length.

Problem Statement

Input: nums (List[int])—array of integers; k (int)—target sum.
Output: Integer—number of contiguous subarrays summing to k.
Rules: Subarrays must be consecutive; count all valid instances.

Constraints

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

Examples

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

Output: 2
Subarrays: [1, 1] (indices 0-1), [1, 1] (indices 1-2).

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

Output: 2
Subarrays: [1, 2] (sum = 3), [3] (sum = 3).

Input: nums = [1,-1,0], k = 0

Output: 3
Subarrays: [1, -1], [-1, 0], [0].

Understanding the Problem: Counting Subarrays

To solve LeetCode 560: Subarray Sum Equals K in Python, we need to count all contiguous subarrays in nums whose elements sum to k. A subarray is a slice of consecutive elements, and with array lengths up to 2 * 10⁴, a brute-force check of all subarrays (O(n²)) is possible but slow. Negative numbers and zeros mean we can’t simply look for positive sums, and k can be any integer. We can optimize using prefix sums and a hash map to track cumulative sums efficiently. We’ll explore:

Best Solution (Hash Map with Prefix Sums): O(n) time, O(n) space—fast and scalable.
Alternative Solution (Brute-Force Nested Loops): O(n²) time, O(1) space—simple but inefficient.

Let’s dive into the hash map solution with a friendly breakdown!

Best Solution: Hash Map with Prefix Sums

Why Hash Map Wins

The hash map with prefix sums is the best for LeetCode 560 because it reduces the problem to O(n) time and O(n) space by using a hash map to store cumulative sums as we scan the array once, counting subarrays ending at each position that sum to k by leveraging the difference between prefix sums. It’s like keeping a running tally of sums and spotting matching pairs on the fly!

How It Works

Think of this as a subarray-sum spotter:

Step 1: Prefix Sum Insight:

For subarray nums[i:j+1], sum = prefix[j] - prefix[i-1].
If sum = k, then prefix[j] - prefix[i-1] = k, or prefix[j] - k = prefix[i-1].

Step 2: Initialize:

Hash map prefix_sums tracks frequency of cumulative sums; start with {0: 1} (empty subarray).

Step 3: Scan Array:

Compute running sum curr_sum.
Check if curr_sum - k exists in map; add its count to result.
Update map with curr_sum.

Step 4: Return Count:

Total number of valid subarrays.

Why It Works:

Prefix sum differences identify all subarrays ending at current position.
Hash map makes lookups O(1).

It’s like a subarray-sum detective!

Step-by-Step Example

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

Init: prefix_sums = {0: 1}, count = 0, curr_sum = 0.
Step 1: Index 0, num = 1:

curr_sum = 1, check 1 - 2 = -1, not in map.
Update: prefix_sums = {0: 1, 1: 1}.

Step 2: Index 1, num = 1:

curr_sum = 2, check 2 - 2 = 0, in map (1), count = 1.
Update: prefix_sums = {0: 1, 1: 1, 2: 1}.

Step 3: Index 2, num = 1:

curr_sum = 3, check 3 - 2 = 1, in map (1), count = 2.
Update: prefix_sums = {0: 1, 1: 1, 2: 1, 3: 1}.

Result: 2.

Example: nums = [1, -1, 0], k = 0

Init: prefix_sums = {0: 1}, count = 0, curr_sum = 0.
Step 1: num = 1:

curr_sum = 1, 1 - 0 = 1, not in map.
prefix_sums = {0: 1, 1: 1}.

Step 2: num = -1:

curr_sum = 0, 0 - 0 = 0, in map (1), count = 1.
prefix_sums = {0: 2, 1: 1}.

Step 3: num = 0:

curr_sum = 0, 0 - 0 = 0, in map (2), count = 3.
prefix_sums = {0: 3, 1: 1}.

Result: 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # Step 1: Initialize hash map and counters
        prefix_sums = {0: 1}  # Key: cumulative sum, Value: frequency
        curr_sum = 0
        count = 0

        # Step 2: Scan array with prefix sums
        for num in nums:
            curr_sum += num  # Update running sum
            # Check if curr_sum - k exists in map
            if curr_sum - k in prefix_sums:
                count += prefix_sums[curr_sum - k]
            # Update map with current sum
            prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1

        # Step 3: Return total count
        return count

Line 4: Map starts with {0: 1} for empty subarray.
Lines 7-15: Iterate array:

Add current number to curr_sum.
If curr_sum - k in map, add its frequency to count.
Increment frequency of curr_sum.

Line 18: Return total subarrays.
Time Complexity: O(n)—single pass with O(1) map lookups.
Space Complexity: O(n)—hash map storage.

It’s like a subarray-sum tally master!

Alternative Solution: Brute-Force Nested Loops

Why an Alternative Approach?

The brute-force nested loops solution checks every possible subarray by iterating all start and end indices, summing elements, and counting matches, running in O(n²) time and O(1) space. It’s simple but slow, making it a good baseline for understanding or small arrays.

How It Works

Picture this as a subarray-sum checker:

Step 1: Iterate all start indices.
Step 2: For each start, sum to all end indices.
Step 3: Count subarrays summing to k.
Step 4: Return total.

It’s like a subarray-sum scanner!

Step-by-Step Example

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

Step 1: Start = 0:

[1] = 1, [1, 1] = 2 (count = 1), [1, 1, 1] = 3.

Step 2: Start = 1:

[1] = 1, [1, 1] = 2 (count = 2).

Step 3: Start = 2:

[1] = 1.

Result: 2.

Code for Brute-Force Approach

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = 0

        # Step 1: Iterate all start indices
        for start in range(n):
            curr_sum = 0
            # Step 2: Sum to all end indices
            for end in range(start, n):
                curr_sum += nums[end]
                if curr_sum == k:
                    count += 1

        # Step 3: Return total count
        return count

Lines 7-12: Nested loops compute all subarray sums, count matches.
Line 15: Return total.
Time Complexity: O(n²)—nested loops.
Space Complexity: O(1)—no extra space.

It’s a brute-force subarray counter!

Comparing the Two Solutions

Hash Map (Best):

Pros: O(n), O(n), fast.
Cons: Extra space.

Brute-Force (Alternative):

Pros: O(n²), O(1), simple.
Cons: Slower.

Hash map wins for speed!

Additional Examples and Edge Cases

[1], k = 1: 1.
[0, 0], k = 0: 3.
[-1, 1], k = 0: 1.

Hash map handles them all!

Complexity Recap

Hash Map: Time O(n), Space O(n).
Brute-Force: Time O(n²), Space O(1).

Hash map’s the efficiency champ!

Key Takeaways

Hash Map: Prefix power—learn at Python Basics!
Brute-Force: Loop clarity.
Arrays: Sums are fun.
Python: Maps or loops, your pick!

Final Thoughts: Count Those Subarrays!

LeetCode 560: Subarray Sum Equals K in Python is a clever array challenge. Hash map with prefix sums is your fast track, while brute-force offers a clear start. Want more? Try LeetCode 1: Two Sum or LeetCode 974: Subarray Sums Divisible by K. Ready to sum? Head to Solve LeetCode 560 on LeetCode and tally those subarrays today!