Поиск минимального подмногообразия из n целых чисел sum >= 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), но алгоритм не находит его.

Можно ли это сделать в линейном времени (с предпочтительной постоянной пространственной сложностью)?

Ответы

Ответ 1

Здесь одно, что линейное время, но и линейное пространство. Дополнительное пространство происходит от дека, который может вырасти до линейного размера. (Там также есть второй массив для хранения кумулятивных сумм, но это можно легко удалить.)

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 также сортируются путем увеличения значения "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.

Во-первых, мы можем исключить S0, если мы когда-нибудь обнаружим, что S1 начинает подходящий сегмент (т.е. сегмент, суммирующий по крайней мере к). Это то, что делает первый цикл while, где start - S0, а startPoints [0] - S1. Даже если мы найдем какой-то будущий подходящий сегмент, начиная с S0, он будет длиннее сегмента, который мы уже нашли, начиная с S1.

Во-вторых, мы можем исключить S0, если сумма элементов из S0 в S1-1 равна &lt = 0 (или, что то же самое, если сумма элементов до S0 >= сумма элементов до S1). Это то, что делает второй цикл while, где S0 - startPoints [-1], а S1 - конец + 1. Обрезка элементов из S0 в S1-1 всегда имеет смысл (для конечных точек на S1 или новее), поскольку она делает сегмент короче без уменьшения его суммы.

На самом деле существует третья ситуация, когда мы могли бы устранить S0: когда расстояние от S0 до конца больше длины самого короткого сегмента, найденного до сих пор. Я не реализовал этот случай, потому что он не нужен.

Ответ 2

Здесь у вас есть псевдокод, предоставляющий решение, которое вы ищете.

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 SUGGESTION

INPUTS: массив целых чисел, индексированный от 0 до endIndex. Целевое значение (k) для сравнения с (targetVal).

OUTPUTS: окончательное добавление выбранного подмножества (maxSumSoFar), индекс начала подмножества (maxStartIndex), конечный индекс подмножества (maxEndIndex), общее количество элементов в подмножестве (minTotSofar).