Finding sequence that maps to a given sum

[hholzer]

given array A and number s, find i,j so sum of A[i..j] = s

Can this be done in linear time? I've thought of using a hashtable
but I would be interested in other methods.

 

[diggy]

Hmm -- you could create an aggregate array to start (n time). But I don't think you can get away from trying all of the options, sumsInArray>s, and doing a search for the difference you want (the series you are searching is monotonic so that should help). That doesn't get you to linear yet though. n + n(s>S)*log(n(s<S))

If you don't mind making a table at the get go and eating n^2, then that would work.