Number of contiguous subsequences summing to a given target
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&lt;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.


Initialize the count of solutions: $N \gets 0$.
Initialize a hash table $H$ containing a single entry: $B[b_0] \gets 1$.
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$.

Return $N$.


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