Determine if a sorted array contains a contiguous sequence that sums up to N

Question

I'm trying to write an algorithm that will return True/False whether a contiguous sequence in a sorted array that contains only positive integers, can sum up to N.

For example:

Array = {  1, 2, 3, 4 };
6 is good! 1 + 2 + 3 = 6
8 is not good! 1 + 3 + 4 = 8, but it's not contiguous, since we skipped the 2.

This is what I have tried to do:

int[] arr = ...;
int headIndex = 1, tailIndex = 0, sum = arr[0];

while (sum != n)
{
    if (sum < n)
    {
        sum += arr[headIndex++];
    }

    if (sum > n)
    {
        sum -= arr[tailIndex++];
    }
}

return sum == n;

Obviously the above does not work (In some cases it might get stuck in an infinite loop). Any suggestions?

One thing I haven't mentioned earlier, and is very important- the algorithm's complexity must be low as possible.

Answer 1

This is just a sketch:

1. Loop from left to right, find the largest k that n1 + ... + nk <= target, set sum = n1 + ... + nk. If the array sum is smaller than target, then return false.
2. If sum == target, we are done. If not, then any subarray S that sum to target will have S.length < k, and will begin from an element that is larger than the first one. So we kick out the first from the sum: sum -= n1, leftEnd++. Now we can go back to step 1, but no need to compute k from scratch.

Since the left end moves at most N times, and the right end moves at most N times, this algorithm has time complexity O(N), and constant space requirement.