❓ Что такое sliding window и когда его применять

Sliding window это приём для задач, где нужно найти подмассив или подстроку, удовлетворяющие условию. Вместо перебора всех пар (i, j) за O(n²) мы поддерживаем окно с двумя границами и двигаем их по условию.

Приём подходит, когда нужно найти минимальную или максимальную длину подмассива с суммой >= target, найти подстроку без повторяющихся символов, найти все анаграммы паттерна в строке. Окно бывает фиксированного размера или динамическим.

// минимальный подмассив с суммой >= target
func minSubarrayLen(target int, nums []int) int {
    left, sum, res := 0, 0, len(nums)+1
    for right := range nums {
        sum += nums[right]
        for sum >= target {
            if right-left+1 < res {
                res = right - left + 1
            }
            sum -= nums[left]
            left++
        }
    }
    if res == len(nums)+1 {
        return 0
    }
    return res
}

🐸 Библиотека Go для собеса