Find the minimum count of elements summing to a pre-defined sum
This can be solved in $O(n \lg n)$ time by computing prefix sums and then using divide-and-conquer.

Step 1. Compute the prefix sums $p_0,p_1,\dots,p_n$, where we define $p_i = a_1 + a_2 + \dots + a_i$.  Throw away the $a_i$'s.  Now the problem becomes: count how many index-pairs $i,j$ there are where $0 \le i \le j \le n$ and $p_j = p_i + s$.

Step 2. Solve this problem using divide-and-conquer.  First, count the number of solutions where $0 \le i \le j \le n/2$ (recursively).  Second, count the number of solutions where $n/2 &lt; i \le j \le n$ (recursively).  Third, count the number of solutions where $0 \le i \le n/2$ and $n/2 &lt; j \le n$.  This third step can be done in $O(n)$ time (expected running time).  Since this is your exercise, I'll let you work out how: it's not too hard. 

The total running time satisfies the recurrence $T(n) = 2 T(n/2) + O(n)$, so this yields a $O(n \lg n)$ time solution.