04 · ДИАПАЗОН

Скользящее окно

Окно поддерживает состояние непрерывного подмассива или подстроки без повторного пересчёта.

3 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Границы

left := 0
for right, value := range nums {
    add(value)
    for windowIsInvalid() {
        remove(nums[left])
        left++
    }
}

Каждый элемент входит и выходит из окна не более одного раза.

Частоты

count := make(map[byte]int)
count[s[right]]++
count[s[left]]--

Map или фиксированный [128]int хранит состояние окна.

Фиксированное окно

sum += nums[right]
if right >= k { sum -= nums[right-k] }
if right >= k-1 { best = max(best, sum) }

Сумма обновляется за O(1), а не пересчитывается за O(k).

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Без повторяющихся символов

Left прыгает за последнее вхождение символа.

O(n) time · O(alphabet) space

solution.go

func lengthOfLongestSubstring(s string) int {
    last := map[byte]int{}
    left, best := 0, 0
    for right := range s {
        if pos, ok := last[s[right]]; ok && pos >= left {
            left = pos + 1
        }
        last[s[right]] = right
        best = max(best, right-left+1)
    }
    return best
}

ПРИМЕР РЕШЕНИЯ

Минимальная длина по сумме

Сжимаем окно, пока сумма достаточна.

O(n) time · O(1) space

solution.go

func minSubArrayLen(target int, nums []int) int {
    left, sum, answer := 0, 0, len(nums)+1
    for right, n := range nums {
        sum += n
        for sum >= target {
            answer = min(answer, right-left+1)
            sum -= nums[left]
            left++
        }
    }
    if answer > len(nums) { return 0 }
    return answer
}

ПРИМЕР РЕШЕНИЯ

Перестановка в строке

Фиксированное окно сравниваем по частотам.

O(n) time · O(1) space

solution.go

func checkInclusion(pattern, s string) bool {
    var need, have [26]int
    for i := range pattern { need[pattern[i]-'a']++ }
    for right := range s {
        have[s[right]-'a']++
        if right >= len(pattern) { have[s[right-len(pattern)]-'a']-- }
        if have == need { return true }
    }
    return false
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Диапазон должен быть непрерывным
Определи условие невалидного окна
Не забудь обновить ответ в правильный момент