Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is an integer array and a target k.

The task is not to find the longest subarray or to return the subarray itself. It is simply to count how many contiguous subarrays add up to k.

That means every start and end position matters. Different subarrays can overlap, and the same value can appear many times.

Why the obvious approaches fall short

The brute-force approach is:

  • choose every possible start index
  • extend the end index to the right
  • compute each subarray sum

That works, but it costs O(n^2) time even if prefix sums are used to make each sum lookup cheap.

A common instinct is to try sliding window, but that does not work in the general case because the array can contain negative numbers.

With negative numbers, expanding the window can make the sum go up or down, and shrinking the window can also make the sum go up or down. That breaks the monotonic behavior sliding window needs.

The key insight

Think in terms of prefix sums.

Let prefix[i] mean the sum of the first i numbers. Then the sum of the subarray from left to right is:

prefix[right + 1] - prefix[left]

For that subarray to equal k, this must be true:

prefix[right + 1] - prefix[left] = k

Rearrange it:

prefix[left] = prefix[right + 1] - k

So while scanning from left to right, once the current running sum is known, the only question is:

how many earlier prefix sums were equal to running_sum - k?

If that count is known immediately, then the number of valid subarrays ending at the current index is known immediately too.

That is why a hash map solves the problem:

  • key: a prefix sum value
  • value: how many times that prefix sum has appeared so far

How to derive the optimal solution

A practical way to derive it is:

  1. Start with brute force and notice it repeatedly recomputes overlapping sums.
  2. Replace repeated summation with a running prefix sum.
  3. Notice that each ending index only needs to know how many earlier prefix sums make the difference equal to k.
  4. Store those earlier prefix sums in a hash map so each lookup is O(1) on average.

There is one small but important initialization detail:

  • start the map with {0: 1}

This means a prefix sum equal to k should count as one valid subarray starting at index 0.

Best approach

The prefix-sum plus hash-map solution is the right default:

  • Time: O(n)
  • Extra space: O(n)
  • Why it is optimal: every element is processed once, and each step only does constant-time bookkeeping

Python solution

from typing import Dict, List


def count_subarrays_with_sum(numbers: List[int], target_sum: int) -> int:
    """Return the number of contiguous subarrays whose sum equals target_sum."""
    prefix_sum_counts: Dict[int, int] = {0: 1}
    running_sum = 0
    matching_subarray_count = 0

    for number in numbers:
        running_sum += number

        # Any earlier prefix sum equal to running_sum - target_sum forms
        # a valid subarray ending at the current position.
        needed_prefix_sum = running_sum - target_sum
        matching_subarray_count += prefix_sum_counts.get(needed_prefix_sum, 0)

        # Record the current prefix sum after counting matches so the
        # current position is not paired with itself.
        prefix_sum_counts[running_sum] = prefix_sum_counts.get(running_sum, 0) + 1

    return matching_subarray_count


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        return count_subarrays_with_sum(numbers=nums, target_sum=k)

Why this works

At each index, the algorithm treats that index as the end of a subarray.

If the current running sum is S, then any earlier prefix sum of S - k creates a subarray whose sum is exactly k. The hash map tells how many such earlier prefix sums exist, so all valid subarrays ending here are counted in one step.

Because the algorithm processes each number once and updates the map once per step, it stays linear.

The interview version to remember is:

track running sum, count how many times running_sum - k has appeared before, then record the current running sum for future subarrays.