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

Ниже приведено решение в виде скользящего окна для нахождения подмассива минимальной длины с суммой больше 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

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


python arrays algorithm sliding-window sub-array
person user11508332    schedule 20.03.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

выход:

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
person Alain T.    schedule 20.03.2020
comment
есть ли способ заставить это иметь дело с отрицательными целыми числами? - person user11508332; 20.03.2020
comment
Решение для отрицательных чисел уже находится в ссылке, которую вы разместили в вопросе. - person Alain T.; 20.03.2020