Number of contiguous subsequences summing to a given target

Question

I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$.

For example, if $A = \{2,5,6,-1\}$ and $k = 5$ then the answer is $2$, since both $5$ and $6,-1$ sum to $5$.

Answer 1

Here is a simple randomized $O(n)$ time algorithm. We start by rephrasing your problem slightly. Suppose that the original array is $a_1,\ldots,a_n$. Form a new array $b_0,\ldots,b_n$ containing the running sums of the previous array: $$ b_0 = 0, \qquad b_i = a_1 + \cdots + a_i. $$ Notice that $a_i + \cdots + a_j = b_j - b_{i-1}$. Therefore we can rephrase the problem as follows:

Given an array $b_0,\ldots,b_n$ and a target $t$, find the number of pairs $i<j$ such that $b_j = b_i + t$.

As an example, if $A = 2,5,6,-1$ then $B=0,2,7,13,12$, and for $t=5$ we get two solutions: $7 - 2 = 12 - 7 = 5$.

The idea now is very simple: we scan $B$ from left to right, and for each $b_j$, we count the number of values $b_j-t$ which have occurred previously, storing them using a hash table.

1. Initialize the count of solutions: $N \gets 0$.
2. Initialize a hash table $H$ containing a single entry: $B[b_0] \gets 1$.
3. For $j = 1,\ldots,n$:
   • If $b_j - t \in B$, let $N \gets N + H[b_j - t]$.
   • If $b_j \notin H$, let $H[b_j] \gets 1$, and otherwise let $H[b_j] \gets H[b_j] + 1$.
4. Return $N$.

The same algorithm can be implemented in deterministic $O(n\log n)$ time using a self-balancing binary search tree.