在线性时间内找到和大于等于k的n个整数的最小子数组

Question

在线性时间内找到和大于等于k的n个整数的最小子数组

pythonalgorithm

11

最近我一直在解决以下问题：

给定一个整数数组，找到一个至少总和为 k 的最小（最短长度）子数组。

很明显，这可以很容易地用 O(n^2) 来完成。我能够编写一个解决自然数线性时间的算法，但我无法解决整数情况。

我最近的尝试是这样的：

def find_minimal_length_subarr_z(arr, min_sum):
    found = False
    start = end = cur_end = cur_sum = 0
    for cur_start in range(len(arr)):
        if cur_end <= cur_start:
            cur_end, cur_sum = cur_start, arr[cur_start]
        else:
            cur_sum -= arr[cur_start-1]
        # Expand
        while cur_sum < min_sum and cur_end < len(arr)-1:
            cur_end += 1
            cur_sum += arr[cur_end]
        # Contract
        while cur_end > cur_start:
            new_sum = cur_sum - arr[cur_end]
            if new_sum >= min_sum or new_sum >= cur_sum:
                cur_end -= 1
                cur_sum = new_sum
            else:
                break
        if cur_sum >= min_sum and (not found or cur_end-cur_start < end-start):
            start, end, found = cur_start, cur_end, True
    if found:
        return start, end

例如：

[8, -7, 5, 5, 4], 12 => (2, 4)

然而，它无法处理以下情况：

[-12, 2, 2, -12, 2, 0], 4

正确的结果是 (1, 2)，但算法无法找到。

这个问题是否可以在线性时间内完成（最好具有恒定的空间复杂度）？

- Thijs van Dien

给它一个名字：这不是 Kadane 算法吗，只是提前终止了吗？ - bitWorking

1

需要注意的一点是，您永远不会想要以负数开始子数组。 - Vaughn Cato

@ThijsvanDien 你是对的。我忽略了这个事实。。 - bitWorking

http://stackoverflow.com/questions/17379047/find-minimal-length-of-sub-array-whose-sum-is-greater-than-k - i Code 4 Food

找到最小的元素并将该元素添加到所有元素中。现在你只有自然元素了。（您的解决方案适用于此）。您只需要修改并询问sum_min + cnt * MIN_VALUE，其中cnt是您在解决方案中使用的元素数量。 - Mark

显示剩余7条评论

2个回答

1

这里有一个伪代码，提供了您正在寻找的解决方案。

curIndex = 0
while (curIndex <= endIndex)
{
    if(curSum == 0)
    {
        startIndex = curIndex
    }

    curSum = curSum + curVal
    curTot = curTot + 1
    if(curSum >= targetVal AND curTot < minTotSofar)
    { 
        maxSumSofar = curSum
        maxStartIndex = startIndex
        maxEndIndex = curIndex
        minTotSofar = curTot
        if(curTot == 1)
        {
            exit_loop
        }

        curSum = 0
        curTot = 0
        curIndex = startIndex   
    }
    else if(curIndex == endIndex)
    {
        if(maxSumSofar == 0 AND curSum >= targetValue)
        {
                maxSumSofar = curSum
                maxStartIndex = startIndex
                maxEndIndex = curIndex
                minTotSofar = curTot
         }
         else if(curSum < targetValue AND startIndex < endIndex)
         {
                curSum = 0
                curTot = 0
                curIndex = startIndex
         }
    }
    curIndex = curIndex + 1
}

------------在JWPAT7建议后更新

输入：整数数组，从0到endIndex索引。目标值（k）与之比较的值（targetVal）。

输出：所选子集的最终加和（maxSumSoFar），子集的起始索引（maxStartIndex），子集的结束索引（maxEndIndex），子集中元素的总数（minTotSofar）。

- varocarbas

代码产生的结果以及其输入并不清晰。或许您可以添加一个过程标题来显示输入，并添加一个返回结果语句来澄清这些问题。 - James Waldby - jwpat7

谢谢您的建议。我已经立即更新了代码。如果需要进一步的说明，请告诉我。 - varocarbas

最初，我错误地编写了一个寻找子集<= k的代码。这就是为什么需要进行所有这些更正。这个版本应该没问题了。对于所有的问题，我表示歉意。 - varocarbas

你说得对。我的错：今天很累，没有仔细思考就写下了我的答案。但是算法提供了正确的解决方案。请记住，我直接用伪代码创建了这个算法，没有任何语言的工作程序。 - varocarbas

把所有的东西都放在注释里有点困难。我用Python实现了你的算法并尝试了一下。伪代码中有一些被省略的东西，可能我实现得不正确。我会在后面的注释中提供更多细节。 - Vaughn Cato

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris Okasaki · Accepted Answer

这里有一个时间复杂度为线性且空间复杂度也是线性的算法。额外的空间来自于双端队列，其大小可能会达到线性级别。（还有第二个数组来维护累加和，但可以很容易地删除。）

from collections import deque
def find_minimal_length_subarr(arr, k):
   # assume k is positive
   sumBefore = [0]
   for x in arr: sumBefore.append(sumBefore[-1] + x)
   bestStart = -1
   bestEnd = len(arr)
   startPoints = deque()
   start = 0
   for end in range(len(arr)):
      totalToEnd = sumBefore[end+1]
      while startPoints and totalToEnd - sumBefore[startPoints[0]] >= k: # adjust start
         start = startPoints.popleft()
      if totalToEnd - sumBefore[start] >= k and end-start < bestEnd-bestStart:
         bestStart,bestEnd = start,end
      while startPoints and totalToEnd <= sumBefore[startPoints[-1]]: # remove bad candidates
         startPoints.pop()
      startPoints.append(end+1) # end+1 is a new candidate
   return (bestStart,bestEnd)

deque保存从左到右的候选开始位置序列。其关键不变量是deque中的位置也按“sumBefore”的递增值排序。

要了解原因，请考虑两个位置x和y，其中x > y，并假设sumBefore[x] <= sumBefore[y]。那么x是比y更好的起始位置（对于以x或以后位置结束的段），因此我们不需要再考虑y。

进一步解释：

想象一个看起来像这样的天真算法：

for end in 0..N-1
   for start in 0..end
      check the segment from start to end

我正在尝试改进内部循环，只考虑特定的起始点而不是所有可能的起始点。那么我们什么时候可以将特定的起始点从进一步考虑中排除？有两种情况。考虑两个起始点S0和S1，其中S0在S1左侧。

首先，如果我们发现S1开始一个符合条件的片段（即，总和至少为k的片段），我们可以消除S0。这就是第一个while循环所做的事情，其中start是S0，startPoints[0]是S1。即使我们找到了一些未来在S0开始的符合条件的片段，它也会比我们已经发现在S1开始的片段更长。

其次，如果从S0到S1-1的元素之和<= 0（或者等价地，如果S0之前的元素之和>= S1之前的元素之和），则可以消除S0。这就是第二个while循环所做的事情，其中S0是startPoints[-1]，S1是end+1。对于从S1或以后的终点，修剪S0到S1-1的元素总是有意义的，因为它可以缩短片段而不降低其总和。

实际上，有第三种情况可以消除S0：当从S0到end的距离大于迄今为止找到的最短片段的长度时。我没有实现这种情况，因为它不是必需的。