python - 在线性时间中找到n个总和> = k的整数的最小子数组

最近，我一直在努力解决以下问题:

给定一个整数数组，请找到一个总和至少为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)，但算法找不到它。

能否完全在线性时间内完成(最好保持恒定的空间复杂度)？

最佳答案

这是线性时间，也是线性空间。多余的空间来自可能会增长到线性大小的双端队列。 (还有第二个数组可以维护累加和，但是可以很容易地删除它。)

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]
进一步说明:

想象一下一个看起来像这样的幼稚算法:

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的元素之和 = S1之前的元素之和)，则可以消除S0。这是第二个while循环所执行的操作，其中S0是startPoints [-1]，S1是end + 1。将元素从S0修剪到S1-1总是有意义的(对于S1或更高版本的端点)，因为这会使段变短而不减小其和。

实际上，在第三种情况下，我们可以消除S0:从S0到末端的距离大于到目前为止找到的最短线段的长度。我没有实现此案例，因为它不是必需的。

关于python - 在线性时间中找到n个总和> = k的整数的最小子数组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17391025/