algorithm - 确定排序数组是否包含总和为 N 的连续序列

Question

我正在尝试编写一个算法，该算法将返回 True/False sorted array 中仅包含正整数的连续序列是否总和为 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)，空间需求不变。