Question: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T Example [23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20 [1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8 [1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7
Note: We are looking for an O(N) solution. There is an obvious O(N^2) solution which is a good starting point but is not the final solution we are looking for.
I introduced sliding window algorithm to my solution to make the calculation efficient.
There are two optimizations worth mentioning in this solution.
The first is that, any value that is exactly equal to the target triggers an immediate return. This skips some wasted iterations, for example:
The second is that any value which is larger than the target and surrounding numbers are skipped because those steps always return false. For example: