Subarray Sum Equals K

Problem in Plain English

Given an integer array and a target k, count how many contiguous non-empty subarrays sum exactly to k. Negative values are allowed, so the window cannot simply grow and shrink.

Problem Statement

Given an integer array nums and an integer k, return the number of contiguous, non-empty subarrays whose elements sum to k. A subarray consists of adjacent indices; it cannot skip a position.

Count occurrences by their start and end indices, including overlapping subarrays. Negative values and zeros are allowed, so moving an endpoint does not necessarily increase or decrease the sum.

Constraints

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

Examples

Example 1

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

The subarrays nums[0..1] and nums[1..2] each sum to 2.

Example 2

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

The subarrays [1, 2] at indices 0..1 and [3] at index 2 each sum to 3.

Example 3

Input: nums = [0, 0, 0], k = 0
Output: 6

All three length-one subarrays, both length-two subarrays, and the whole length-three array sum to zero: 3 + 2 + 1 = 6. The empty subarray is not counted.

Example 4

Input: nums = [1, -1, 1], k = 1
Output: 3

The single elements at indices 0 and 2 each sum to one, and the entire array also sums to one. Repeated prefix totals represent different start boundaries.

Example 5

Input: nums = [2], k = 0
Output: 0

The only non-empty subarray sums to two. A zero-length interval must not be counted when k is zero.

Intuition

A prefix sum is the total before a boundary in the array. Subtracting two boundary totals leaves exactly the values between them. For [1, 1, 1], the boundary totals are [0, 1, 2, 3]; differences 2 - 0 and 3 - 1 each give k = 2. At a current total P, every earlier boundary with total P - k starts a matching subarray. A frequency map counts those earlier boundaries, even when several share the same total.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Try every start index and extend the end one position at a time, carrying the running sum instead of adding the whole interval again. This avoids a third loop, but still examines a quadratic number of start/end pairs.

Step-by-Step Logic

Initialize count to zero. For each start index, reset a running sum to zero; Example 1 uses [1, 1, 1] and k = 2.
For each end index from start through the final element, add nums[end] to the running sum. If the sum equals k, increment count.
At start 0, the sums are 1, 2, 3; count increases to 1 at end 1. Continue after a match or after exceeding k, because zeros and negatives can create further matches.
Reset the sum at start 1: sums 1, 2 add one more match. Start 2 produces only sum 1.
Return count 2 after all non-empty intervals have been checked.

Why It Works

Each non-empty contiguous subarray has exactly one start/end pair with start no greater than end. The nested loops visit each such pair once, and the running sum contains exactly nums[start] through nums[end]. Incrementing only when that sum equals k counts every valid interval once, including overlapping ones and intervals with negative values.

Dry Run

Brute Force: variable states at each step
start	end	Value added	Sum before	Sum after	Matches k=2?	count after
`0`	`0`	`1`	`0`	`1`	no	`0`
`0`	`1`	`1`	`1`	`2`	yes	`1`
`0`	`2`	`1`	`2`	`3`	no	`1`
`1`	`1`	`1`	`0` after reset	`1`	no	`1`
`1`	`2`	`1`	`1`	`2`	yes	`2`
`2`	`2`	`1`	`0` after reset	`1`	no; return	`2`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Let n be the length. There are n(n + 1)/2 non-empty start/end pairs, each doing one addition and comparison, so time is O(n^2). Only two indices, a running sum, and the count are stored, giving O(1) extra space. Recomputing each interval from scratch would take O(n^3), which this code avoids.

Code

Solution.java

1class Solution {2    public int subarraySum(int[] nums, int k) {3        int count = 0;4        for (int start = 0; start < nums.length; start++) {5            int sum = 0;6            for (int end = start; end < nums.length; end++) {7                sum += nums[end];8                if (sum == k) {9                    count++;10                }11            }12        }13        return count;14    }15}

Hints

Hint 1

For a fixed ending index, can you express a subarray sum as the difference of two totals from the beginning?

Hint 2

If the current total is P, an earlier total P - k starts a matching interval. More than one earlier boundary can have that total.

Hint 3

Store prefix frequencies beginning with {0: 1}. Add the frequency of P - k to the answer before inserting the current P.

Edge Cases

One element: [2] with k = 2 returns 1; with k = 0 it returns 0. Empty arrays are outside the constraints.
All zeros: [0, 0, 0] with k = 0 returns 6, since every non-empty interval qualifies. At the maximum length of 20000, the count is 200010000.
Negative values: [1, -1, 1] with k = 1 returns 3; the same prefix total can appear at several different boundaries.
A whole-array match, such as [1, 1, 1] with k = 3, relies on the initial prefix frequency {0: 1}.
A negative target is valid: [-1, -1, 1] with k = -1 has three matching subarrays. Large targets with no match must return zero.

Common Mistakes and Interview Tips

Using a set instead of frequencies loses separate start boundaries with equal prefix totals. For three zeros, each new zero matches every earlier boundary.
Inserting the current prefix before looking up the difference counts an empty interval when k = 0. Look up first, insert second.
Omitting {0: 1} loses intervals beginning at index 0; adding a separate whole-prefix check while keeping the seed double-counts those intervals.
Stopping when the running sum exceeds k or using an ordinary grow/shrink sliding window assumes monotonic sums. Negatives break that assumption; zeros also require care when counting all intervals.
Interview tip: derive current - earlier = k, then explain why the map holds only earlier prefixes and why it stores counts. The optimization improves quadratic time to expected linear time while adding O(n) storage.

Key Takeaway

For contiguous-sum counting, a prefix difference turns each ending position into a search for earlier totals. A hash map of frequencies counts every valid start, including repeated prefix values, while lookup-before-insertion keeps intervals non-empty.