确定排序数组是否包含总计N的连续序列

Question

我正在尝试编写一个算法,它将返回True/False一个排序数组中只包含正整数的连续序列,可以求和N.

例如:

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.

这是我试图做的:

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;

显然上面的方法不起作用(在某些情况下,它可能会陷入无限循环).有什么建议？

我之前没有提到的一件事,非常重要 - 算法的复杂性必须尽可能低.

Answer 1

这只是一个草图:

1. 从左到右循环,找到最大的k那个n1 + ... + nk <= target,设置sum = n1 + ... + nk.如果数组和小于target,则返回false.
2. 如果sum == target,我们完成了.如果不是,则任何S总和为的子数组target将具有S.length < k,并且将从大于第一个的元素开始.所以我们从总和中踢出第一个:sum -= n1, leftEnd++. 现在我们可以回到第1步,但不需要k从头开始计算.

由于左端最多移动N次,而右端移动最多N次,因此该算法具有时间复杂度O(N)和恒定空间要求.