Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding sequence that maps to a given sum

  1. Sep 9, 2010 #1
    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.
  2. jcsd
  3. Sep 10, 2010 #2
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook