Subarray Sums I (Editorial)

Let's implement a sliding window using two pointers, $i$ and $j$. For each fixed i = 1, 2, ..., expand the interval $[i...j]$ as much as possible so that the sum of its elements does not exceed $x$. In other words, for each $i$, search for the largest possible $j$ such that the sum of elements in the interval $[i...j]$ does not exceed $x$, while the sum of elements in the interval [i ... j + 1] exceeds $x$.

Let $s$ be the sum of numbers in the interval $[i...j]$. If s + a[j + 1] \le m, expand the interval to [i ... j + 1]. Otherwise, shrink it to [i + 1 ... j]. Count the number of intervals with a sum of $x$.

Example

Let's examine the movement of the pointers for the given example.

1. i = 0, $j$ moves forward until the sum of the numbers in the interval $[i...j]$ exceeds x = 7. We stop at the interval $[\mathrm{0...2}]$, since the sum of the numbers in it is $7$, while in the interval $[\mathrm{0...3}]$, the sum of the numbers is already $9$.

   

2. i = 1, $j$ moves forward to $3$. The sum of the numbers in the interval $[\mathrm{1...3}]$ is $7$, while in the interval $[\mathrm{1...4}]$, it is already $14$.

3. i = 2, the considered interval is $[\mathrm{2...3}]$. The sum of the numbers in it is $3$, but we cannot move the index $j$ forward because the sum of the numbers in the interval $[\mathrm{2...4}]$ is $10$, which is greater than x = 7.

   

4. i = 3, the considered interval is $[\mathrm{3...3}]$. The sum of the numbers in it is $2$, but we cannot move the index $j$ forward because the sum of the numbers in the interval $[\mathrm{3...4}]$ is $9$, which is greater than x = 7.

5. i = 4, the considered interval is $[\mathrm{4...4}]$. The sum of the numbers in it is $7$.

The number of subarrays with a sum of x = 7 is $3$. They start at indices $0,1$, and $4$.

Algorithm realization

Declare an array.

#define MAX 200001
long long a[MAX];

Read the input data.

scanf("%d %lld", &n, &x);
for (i = 0; i < n; i++)
  scanf("%lld", &a[i]);

Initially, set the current interval [i ... j] = [0; 0]. The sum of the numbers in this interval is s = 0.

s = j = 0;

For each value of $i$, sequentially process the intervals $[i...j]$.

for (i = 0; i < n; i++)
{

For the fixed left end $i$ of the interval $[i...j]$, search for the largest $j$ such that the sum of elements in this interval does not exceed $x$.

  while ((j < n) && (s + a[j] <= x)) s += a[j++];

If the sum of the numbers $s$ in the current interval $[i...j]$ equals $x$, increase the desired subarray count $cnt$ by $1$.

  if (s == x) cnt++;

Recompute the sum $s$ for the interval [i + 1 ... j].

  s -= a[i];
}

Print the answer.

printf("%lld\n", cnt);