Editorial for Subarray Sums

Approach

Let $p_i$ be the prefix sum of the first $i$ elements, with $p_0 = 0$. The sum of the subarray from $l$ to $r$ is $p_r - p_{l-1}$.

So when we are at a prefix sum $p_r$, we need to know how many earlier prefix sums equal $p_r - x$. Every such earlier prefix sum gives one subarray ending at $r$ whose sum is $x$.

We scan the array from left to right, maintain the current prefix sum, and store how many times each prefix sum has appeared in a dictionary.

This is $O(n)$ time.

Solution (Python)

n, x = map(int, input().split())
values = list(map(int, input().split()))

seen = {0: 1}
prefix = 0
answer = 0

for value in values:
    prefix += value
    answer += seen.get(prefix - x, 0)
    seen[prefix] = seen.get(prefix, 0) + 1

print(answer)