# Number of contiguous subsequences summing to a given target

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$$.

• Perhaps this can be used as hint: Subsequence sum, from our sisters at stackoverflow. – Hendrik Jan Dec 16 '18 at 16:14

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 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.