алгоритм скользящего окна - условие для запуска <n - PullRequest
Новая
       95

алгоритм скользящего окна - условие для запуска <n

0 голосов
/ 20 марта 2020

Ниже приведено решение для скользящего окна для поиска подмассива минимальной длины с суммой, превышающей x от geeksforgeeks (https://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/) 

# O(n) solution for finding smallest 
# subarray with sum greater than x 

# Returns length of smallest subarray 
# with sum greater than x. If there  
# is no subarray with given sum, then 
# returns n + 1 
def smallestSubWithSum(arr, n, x): 

    # Initialize current sum and minimum length 
    curr_sum = 0
    min_len = n + 1

    # Initialize starting and ending indexes 
    start = 0
    end = 0
    while (end < n): 

        # Keep adding array elements while current 
        # sum is smaller than x 
        while (curr_sum <= x and end < n): 
            curr_sum += arr[end] 
            end+= 1

        # If current sum becomes greater than x. 
        while (curr_sum > x and start < n): 

            # Update minimum length if needed 
            if (end - start < min_len): 
                min_len = end - start  

            # remove starting elements 
            curr_sum -= arr[start] 
            start+= 1

    return min_len

Я проверил, что это решение может работать, но меня смущает, почему в последнее время, когда l oop, запуск проверяется на наличие меньше, чем n - вы не хотите, чтобы он был меньше конца, иначе запуск может go за концом, что не неужели для меня нет смысла?

1 Ответ

0 голосов
/ 20 марта 2020

Поскольку curr_sum был создан путем добавления элементов до конца, он достигнет нуля (или будет меньше x), прежде чем start достигнет конца. Это выйдет, пока l oop. Это также подразумевает, что алгоритм, вероятно, не будет работать с отрицательными числами в массиве.

Лично я написал бы это немного по-другому. Вот пример с учетом условия отрицательного числа: 

def minSub(arr,x):
    subTotal      = 0
    size,minSize  = 0,len(arr)+1
    start         = iter(arr)
    for value in arr:
        subTotal += value
        size     += 1
        while subTotal not in range(0,x+1):
            if subTotal>x :
                minSize = min(minSize,size)
            subTotal -= next(start,0)
            size     -= 1
    return minSize

output: 

arr  = [1, 4, 45, 6, 0, 19] 
x    = 51 
print(minSub(arr,x)) #3

arr = [-8, 1, 4, -1, 3, -6]
x   = 6 
print(minSub(arr,x)) # 4

arr = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
x   = 280 
print(minSub(arr,x)) # 4

arr = [1, 10, 5, 2, 7]
x   = 9
print(minSub(arr,x)) # 1

arr = [1, 2, 4]
x   = 8
print(minSub(arr,x)) # 4
...