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

  • 1
    $\begingroup$ Perhaps this can be used as hint: Subsequence sum, from our sisters at stackoverflow. $\endgroup$ – 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<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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.