Дан массив положительных целых чисел nums и целое число target. Найдите минимальную длину непрерывного подмассива, сумма элементов которого больше или равна target. Если такого подмассива нет, верните 0.

Условие

Дан массив положительных целых чисел nums и целое число target. Найдите минимальную длину непрерывного подмассива, сумма элементов которого больше или равна target. Если такого подмассива нет, верните 0.
Пример: nums = [2, 3, 1, 2, 4, 3], target = 7 → ответ 2 (подмассив [4, 3]).

[1, 1, 7, 5, 2, 9] target 7
[1, 1, 3, 1, 1] t = 5

func minSubArray(nums []int, target int) int { left, sum := 0, 0 minLen := len()

for right, value := range nums {
    sum += value

    for sum >= target {
        if lenght := right - left +1; lenght < minLen {
            minLen = lenght
        }
        sum -= nums[left]
        left++
    }
}

if minLen == len(nums)+1 {
    return 0
}

return minLen

}

Ответ

Используйте скользящее окно: расширяйте его справа, а при достижении target сокращайте слева. Для положительных чисел это O(n) времени и O(1) памяти.

В исходнике нужно заменить len() на len(nums)+1. Ниже сумма хранится в uint64: перед добавлением она меньше положительного target, поэтому два положительных значения int не переполняют uint64.

func minSubArray(nums []int, target int) int {
    if len(nums) == 0 { return 0 }
    if target <= 0 { return 1 }
    left, best := 0, len(nums)+1
    var sum uint64
    for right, value := range nums {
        sum += uint64(value)
        for sum >= uint64(target) {
            if size := right-left+1; size < best { best = size }
            sum -= uint64(nums[left])
            left++
        }
    }
    if best == len(nums)+1 { return 0 }
    return best
}

Предусловие — все элементы строго положительные. Каждый индекс проходит окно не более двух раз. Ответы для трёх примеров: 2, 1 и 3. С отрицательными числами этот алгоритм неприменим.