Answer Define A[i] := sum(A[0:i+1)] create a set B Iterate for each val in A Return True if (target - val) in B otherwise, add val to B return False if none found

Typo, it should be (val - target) in B. Runtime and space are both linear

This is just a straightforward sliding window problem. The keyword here is "contiguous".