3

我正在尝试编写一种算法，该算法将返回仅包含正整数的排序数组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;

显然上述方法不起作用（在某些情况下它可能会陷入无限循环）。有什么建议么？

一件事我之前没有提到，而且非常重要——算法的复杂度必须尽可能低。

4

5 回答 5

8

这只是一个草图：

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

由于左端最多移动 N 次，右端最多移动 N 次，因此该算法的时间复杂度为 O(N)，且空间要求恒定。

于 2013-05-14T21:09:00.687 回答
0

我认为最佳算法适用于在列表上移动的窗口。窗口的值 (WV) 是落在窗口内的元素的总和。如果 WV 小于 N，则移动头部并将适合窗口内的新值添加到 WV，如果该值大于 N，则将尾部向上移动一个并从 WV 中减去落在窗口中的值。当 WV 等于 N，或者尾部超出头部，或者头部在列表的末尾，并且 WV 仍然很低时，算法停止。

这将在线性时间内运行：列表中的每个元素都添加一次，最多减去一次。

写在一些代码中来说明这个想法（类似python），但未经测试

WV = list[0]
L = len(list)
tail = 0
head = 0

while WV != N
  if WV < N
    head += 1
    if head < L
       WV += list[head]
    else
      return false // beyond end of list
  elif WV > N
    if tail < head
       WV -= list[tail]
       tail += 1
    else
      return false // single element bigger then N, and list is sorted

return true
于 2013-05-14T22:30:37.927 回答
0

这是代码中的解决方案。它深受@Ziyao Wei 的草图的影响，这简化了我原来的方法（特别是，没有必要回溯并重新添加小数字，只需按照我最初的想法将它们删除）。

public static bool HasConsecutiveSum(IList<int> list, int requiredSum)
{
    int start = 0;
    int sum = 0;

    for (int end = 0; end < list.Count; end++)
    {
        sum += list[end];

        while (sum > requiredSum)
        {
            sum -= list[start++];
            if (start > end)
            {
                return false;
            }
        }

        if (sum == requiredSum)
        {
            return true;
        }        
    }

    return false;
}
于 2013-05-14T22:18:36.427 回答
0

简单地：

for i = 1 to n - 1:
   j = 0
   while (j < i):
      sm = 0
      for k = j to i:
        sm = sm + array[k]
      if sm == N:
        return True
      j = j + 1
return False

这在O(n^3)时间内有效。

于 2013-05-14T20:46:16.173 回答
0 
var i = 0;
while(i != arr.Length)
{
    var remembre = i;
    var tmp = 0;
    for(; tmp < N && i < arr.Length; ++i)
        tmp += arr[i];
    if(N == tmp)
        return true;
    i = remembre + 1;
}
return false;

我相信这应该有效。

于 2013-05-14T20:49:02.213 回答