Subarray Sum Equals K

Problem

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

Examples

The brute-force approach

Try every pair of indices (i, j) and compute the sum of nums[i..j]. Count pairs where the sum equals k.

count = 0
for i in range(n):
    total = 0
    for j in range(i, n):
        total += nums[j]
        if total == k:
            count += 1
return count

O(n²) — for every start index i you scan to the end. For n=100,000 that's 5 billion additions.

Spotting the pattern

This is a Prefix Sum problem. The key question to ask yourself:

If you know the running prefix sum at position j, what earlier prefix sum would make the subarray between that earlier position and j sum to k?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.