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)但算法找不到。

这完全可以在线性时间内完成（最好具有恒定的空间复杂度）吗？

4

2 回答 2

7

这是一个线性时间和线性空间。额外的空间来自可以增长到线性大小的双端队列。（还有第二个数组来维护累积和，但可以很容易地删除它。）

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)

双端队列包含从左到右的候选起始位置序列。关键不变式是双端队列中的位置也通过增加“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。修剪从 S0 到 S1-1 的元素总是有意义的（对于 S1 或更晚的端点），因为它使段更短而不会减少其总和。

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

于 2013-06-30T16:29:23.123 回答
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 建议后更新

INPUTS：整数数组，索引从 0 到endIndex. 与 ( )比较的目标值 (k targetVal)。

输出：所选子集的最终添加 ( maxSumSoFar)、子集的开始索引 ( maxStartIndex)、子集的结束索引 ( maxEndIndex)、子集中元素的总数 ( minTotSofar)。

于 2013-06-30T14:18:36.107 回答