Два указателя и скользящее окно

Два указателя и скользящее окно простыми словами: встречные и попутные указатели, окно переменной ширины — и на каких хранилищах приём остаётся линейным в Java, Go, JavaScript и Python.

Опубликовано 24 августа 2026 обновлено 6 октября 2026 ~21 мин чтения

← назад к разделу

Мы разобрали массивы и научились мерить скорость O-нотацией. Теперь возьмём самый частый приём, который превращает медленное решение в быстрое: два указателя. Идея простая — вместо двух вложенных циклов пройти по данным один раз, держа в них две подвижные метки.

Приём срабатывает не всегда, и главное здесь — научиться узнавать, когда он применим.

Проблема: вложенные циклы дорогие

Пусть в каталоге отсортированы цены и надо найти две позиции, дающие в сумме ровно номинал сертификата. Самое очевидное решение — перебрать все пары:

for (int i = 0; i < prices.length; i++) {
    for (int j = i + 1; j < prices.length; j++) {
        if (prices[i] + prices[j] == target) return new int[]{i, j};
    }
}

for i := 0; i < len(prices); i++ {
	for j := i + 1; j < len(prices); j++ {
		if prices[i]+prices[j] == target {
			return [2]int{i, j}
		}
	}
}

for (let i = 0; i < prices.length; i++) {
  for (let j = i + 1; j < prices.length; j++) {
    if (prices[i] + prices[j] === target) return [i, j];
  }
}

for i in range(len(prices)):
    for j in range(i + 1, len(prices)):
        if prices[i] + prices[j] == target:
            return i, j

Это O(N²). На тысяче позиций — около полумиллиона пар, ещё терпимо. На миллионе позиций — полтриллиона, то есть часы. А данные уже отсортированы, и мы этим никак не пользуемся.

Встречные указателиспросят на собеседовании

Поставим одну метку в начало, другую в конец и посмотрим на сумму:

сумма больше нужной — единственный способ её уменьшить — сдвинуть правую метку влево, к меньшим ценам;
сумма меньше — двигаем левую метку вправо;
совпало — ответ найден.

Метки идут навстречу: сумма больше цели — правая сдвигается влево, меньше — левая вправо. Пять шагов вместо пятнадцати пар полного перебора — ровно то, что печатает пример ниже.

Тот же проход целиком, с выводом каждой проверенной пары:

живой пример

public class TwoPointers {
    public static void main(String[] args) {
        int[] prices = {4, 9, 15, 22, 30, 41};
        int target = 37;
        int left = 0;
        int right = prices.length - 1;
        int steps = 0;
        while (left < right) {
            steps++;
            int sum = prices[left] + prices[right];
            System.out.println(prices[left] + " + " + prices[right] + " = " + sum);
            if (sum == target) break;
            if (sum < target) left++;
            else right--;
        }
        int pairs = prices.length * (prices.length - 1) / 2;
        System.out.println("шагов: " + steps + ", пар при полном переборе: " + pairs);
    }
}

Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

package main

import "fmt"

func main() {
	prices := []int{4, 9, 15, 22, 30, 41}
	target := 37
	left, right, steps := 0, len(prices)-1, 0
	for left < right {
		steps++
		sum := prices[left] + prices[right]
		fmt.Printf("%d + %d = %d\n", prices[left], prices[right], sum)
		if sum == target {
			break
		}
		if sum < target {
			left++
		} else {
			right--
		}
	}
	pairs := len(prices) * (len(prices) - 1) / 2
	fmt.Printf("шагов: %d, пар при полном переборе: %d\n", steps, pairs)
}

Запустить

живой пример

const prices = [4, 9, 15, 22, 30, 41];
const target = 37;
let left = 0;
let right = prices.length - 1;
let steps = 0;
while (left < right) {
  steps++;
  const sum = prices[left] + prices[right];
  console.log(`${prices[left]} + ${prices[right]} = ${sum}`);
  if (sum === target) break;
  if (sum < target) left++;
  else right--;
}
const pairs = prices.length * (prices.length - 1) / 2;
console.log(`шагов: ${steps}, пар при полном переборе: ${pairs}`);

Запустить

живой пример

prices = [4, 9, 15, 22, 30, 41]
target = 37
left, right, steps = 0, len(prices) - 1, 0
while left < right:
    steps += 1
    total = prices[left] + prices[right]
    print(f"{prices[left]} + {prices[right]} = {total}")
    if total == target:
        break
    if total < target:
        left += 1
    else:
        right -= 1
pairs = len(prices) * (len(prices) - 1) // 2
print(f"шагов: {steps}, пар при полном переборе: {pairs}")

Запустить

Каждый шаг сдвигает одну из меток, и они движутся навстречу — значит, шагов не больше N. Получили O(N) вместо O(N²), без дополнительной памяти.

Почему это законно: сдвигая правую метку влево, мы отбрасываем все пары с этой ценой и любой левее — но все они дают сумму ещё больше, значит заведомо не подходят. На каждом шаге отбрасывается только заведомо ненужное — в этом вся суть приёма.

Обязательное условие — упорядоченность. На неотсортированных данных «сумма больше — двигаем правую метку» ничего не гарантирует: слева может лежать что угодно. Если порядка нет, приём не применим — там выручает хеш-таблица.

Две вариации, которые встречаются сразу после базовой. Если совпадения может не быть вовсе, цикл while (left < right) заканчивается молча, и это надо предусмотреть: либо вернуть «не найдено» после цикла, либо, если задача про ближайшую сумму, на каждом шаге запоминать пару с наименьшей разницей от цели и вернуть её в конце; движение меток при этом то же самое. И тот же приём переносится с пары на тройку: фиксируют первый элемент, а среди остальных ищут пару встречными метками; внешний цикл по первому элементу даёт O(N²) вместо O(N³) полного перебора, и это лучшая известная оценка для задачи о трёх слагаемых на отсортированном массиве.

Попутные указатели

Второй вариант: обе метки идут в одну сторону, но с разной скоростью. Классический пример — убрать повторы в отсортированном массиве, ничего не выделяя дополнительно.

Медленная метка отмечает место, куда писать; быстрая читает подряд:

static int dedup(int[] codes) {
    if (codes.length == 0) return 0;
    int write = 0;
    for (int read = 1; read < codes.length; read++) {
        if (codes[read] != codes[write]) {
            write++;
            codes[write] = codes[read];
        }
    }
    return write + 1;
}

func dedup(codes []int) int {
	if len(codes) == 0 {
		return 0
	}
	write := 0
	for read := 1; read < len(codes); read++ {
		if codes[read] != codes[write] {
			write++
			codes[write] = codes[read]
		}
	}
	return write + 1
}

function dedup(codes) {
  if (codes.length === 0) return 0;
  let write = 0;
  for (let read = 1; read < codes.length; read++) {
    if (codes[read] !== codes[write]) {
      write++;
      codes[write] = codes[read];
    }
  }
  return write + 1;
}

def dedup(codes: list[int]) -> int:
    if not codes:
        return 0
    write = 0
    for read in range(1, len(codes)):
        if codes[read] != codes[write]:
            write += 1
            codes[write] = codes[read]
    return write + 1

Тот же приём с разной скоростью решает и задачу о цикле в связном списке: медленная метка шагает по одному узлу, быстрая по два. Если список замкнулся в кольцо, быстрая рано или поздно догонит медленную — расстояние между ними сокращается на шаг за итерацию. Если кольца нет, быстрая просто упрётся в конец.

Скользящее окно фиксированной ширины

Частный случай попутных указателей — когда между метками держат отрезок постоянной длины. Нужно найти наибольшую сумму k подряд идущих дней выручки.

Наивно — для каждого начала сложить k чисел: O(N·k). Но соседние окна отличаются всего двумя днями: один вошёл, один вышел. Значит, сумму не надо считать заново — её достаточно поправить:

long sum = 0;
for (int i = 0; i < k; i++) sum += revenue[i];
long best = sum;
for (int i = k; i < revenue.length; i++) {
    sum += revenue[i] - revenue[i - k];
    best = Math.max(best, sum);
}

sum := 0
for i := 0; i < k; i++ {
	sum += revenue[i]
}
best := sum
for i := k; i < len(revenue); i++ {
	sum += revenue[i] - revenue[i-k]
	best = max(best, sum)
}

let sum = 0;
for (let i = 0; i < k; i++) sum += revenue[i];
let best = sum;
for (let i = k; i < revenue.length; i++) {
  sum += revenue[i] - revenue[i - k];
  best = Math.max(best, sum);
}

total = sum(revenue[:k])
best = total
for i in range(k, len(revenue)):
    total += revenue[i] - revenue[i - k]
    best = max(best, total)

O(N) и никакой дополнительной памяти. Типичная ошибка — начать с best = 0: если вся выручка отрицательная, ноль окажется «лучшим» ответом, которого на самом деле не существует.

Окно переменной шириныспросят на собеседовании

Самый интересный вариант: ширина окна не задана, её диктует условие. Например, найти самый длинный отрезок ленты, в котором ни одна категория не повторяется.

Правый край всегда идёт вперёд и расширяет окно. Левый край подтягивается только тогда, когда условие нарушено — то есть когда новый символ уже есть в окне. Тогда выкидываем символы слева по одному, пока повтор не уйдёт. Окно на каждом шаге видно в выводе:

живой пример

import java.util.HashSet;
import java.util.Set;

public class Window {
    public static void main(String[] args) {
        String feed = "abcabcbb";
        Set<Character> window = new HashSet<>();
        int left = 0;
        int best = 0;
        for (int right = 0; right < feed.length(); right++) {
            char ch = feed.charAt(right);
            while (window.contains(ch)) {
                window.remove(feed.charAt(left));
                left++;
            }
            window.add(ch);
            best = Math.max(best, right - left + 1);
            System.out.println("окно: " + feed.substring(left, right + 1));
        }
        System.out.println("самый длинный отрезок без повторов: " + best);
    }
}

Запустить

живой пример

package main

import "fmt"

func main() {
	feed := "abcabcbb"
	window := map[byte]bool{}
	left, best := 0, 0
	for right := 0; right < len(feed); right++ {
		ch := feed[right]
		for window[ch] {
			delete(window, feed[left])
			left++
		}
		window[ch] = true
		best = max(best, right-left+1)
		fmt.Println("окно:", feed[left:right+1])
	}
	fmt.Println("самый длинный отрезок без повторов:", best)
}

Запустить

живой пример

const feed = "abcabcbb";
const inWindow = new Set();
let left = 0;
let best = 0;
for (let right = 0; right < feed.length; right++) {
  const ch = feed[right];
  while (inWindow.has(ch)) {
    inWindow.delete(feed[left]);
    left++;
  }
  inWindow.add(ch);
  best = Math.max(best, right - left + 1);
  console.log("окно:", feed.slice(left, right + 1));
}
console.log("самый длинный отрезок без повторов:", best);

Запустить

живой пример

feed = "abcabcbb"
window: set[str] = set()
left = best = 0
for right, ch in enumerate(feed):
    while ch in window:
        window.remove(feed[left])
        left += 1
    window.add(ch)
    best = max(best, right - left + 1)
    print("окно:", feed[left:right + 1])
print("самый длинный отрезок без повторов:", best)

Запустить

Внутри for стоит while, но это не O(N²): каждый символ один раз входит в окно справа и один раз выходит слева, так что всех шагов не больше 2N.

Есть ускорение: помнить, где символ встречался в последний раз, и прыгать левым краем сразу за это место, не выкидывая символы по одному. Здесь прячется самая частая ошибка приёма: левый край нельзя двигать назад. На строке abba у последней a прошлое вхождение стоит в самом начале, а окно к тому моменту уже начинается позже. Прыжок туда откатил бы левый край на позицию 1, окно стало бы bba, и ответ вырос бы до трёх. Поэтому прыгают, только если прошлое вхождение лежит внутри окна: seen >= left. Этот вариант разобран в задаче «Лента без повторов».

Вариант с while общий, и именно он нужен в задачах вида «самый длинный отрезок, где не больше K различных значений»: там нельзя прыгнуть сразу, потому что нарушение снимается постепенно, по одному элементу с левого края.

живой пример

import java.util.HashMap;
import java.util.Map;

public class KDistinct {
    public static void main(String[] args) {
        int[] categories = {1, 2, 1, 2, 3, 2, 2, 4};
        int k = 2;
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < categories.length; right++) {
            count.merge(categories[right], 1, Integer::sum);
            while (count.size() > k) {
                int gone = categories[left++];
                if (count.merge(gone, -1, Integer::sum) == 0) count.remove(gone);
            }
            best = Math.max(best, right - left + 1);
        }
        System.out.println("самый длинный отрезок с не более чем " + k + " категориями: " + best);
    }
}

Запустить

живой пример

package main

import "fmt"

func main() {
	categories := []int{1, 2, 1, 2, 3, 2, 2, 4}
	k := 2
	count := map[int]int{}
	left, best := 0, 0
	for right := 0; right < len(categories); right++ {
		count[categories[right]]++
		for len(count) > k {
			gone := categories[left]
			left++
			count[gone]--
			if count[gone] == 0 {
				delete(count, gone)
			}
		}
		best = max(best, right-left+1)
	}
	fmt.Printf("самый длинный отрезок с не более чем %d категориями: %d\n", k, best)
}

Запустить

живой пример

const categories = [1, 2, 1, 2, 3, 2, 2, 4];
const k = 2;
const count = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < categories.length; right++) {
  count.set(categories[right], (count.get(categories[right]) ?? 0) + 1);
  while (count.size > k) {
    const gone = categories[left++];
    const rest = count.get(gone) - 1;
    if (rest === 0) count.delete(gone);
    else count.set(gone, rest);
  }
  best = Math.max(best, right - left + 1);
}
console.log(`самый длинный отрезок с не более чем ${k} категориями: ${best}`);

Запустить

живой пример

from collections import Counter

categories = [1, 2, 1, 2, 3, 2, 2, 4]
k = 2
count = Counter()
left = best = 0
for right, category in enumerate(categories):
    count[category] += 1
    while len(count) > k:
        gone = categories[left]
        left += 1
        count[gone] -= 1
        if count[gone] == 0:
            del count[gone]
    best = max(best, right - left + 1)
print(f"самый длинный отрезок с не более чем {k} категориями: {best}")

Запустить

Шаблон один и тот же для всех окон переменной ширины: правый край расширяет окно и обновляет счётчики, while сжимает левый край, пока условие нарушено, и после него окно снова верное, а ответ обновляют либо после сжатия (для «не больше»), либо внутри него (для «не меньше»).

Как узнать приём в задачеспросят на собеседовании

Признаки, по которым стоит вспомнить про два указателя:

в условии есть слова «отрезок подряд», «подмассив», «подстрока» — почти наверняка окно;
данные отсортированы, и ищется пара или тройка с нужным свойством — встречные указатели;
надо переставить или отфильтровать элементы на месте, без дополнительной памяти — попутные указатели;
наивное решение — два вложенных цикла, и при переходе к соседнему варианту пересчитывается почти то же самое.

И признак того, что приём не подойдёт: порядок элементов не важен либо ответ требует произвольного доступа к уже пройденным данным — тогда нужна хеш-таблица или префиксные суммы.

Как это сделано в стандартной библиотеке

Сами приёмы из этой статьи пишут руками: готового «скользящего окна» в стандартной библиотеке нет и быть не может — его форма зависит от условия задачи. А вот то, по чему бегают указатели, давно написано и обкатано. И выбор хранилища здесь решает, останется решение линейным или незаметно станет квадратичным.

Эталонная реализация массива в Java — ArrayList. Внутри у него самый обычный массив, который подменяется на больший — примерно в полтора раза длиннее, — когда места перестаёт хватать. Поэтому get(i) стоит O(1), add в конец — O(1) амортизированно (редкий дорогой переезд размазывается по всем добавлениям), а вставка и удаление в середине — O(N): соседей приходится сдвигать.

Указателям нужен ровно доступ по индексу за O(1), так что по ArrayList они бегают с той же скоростью, что по массиву. А вот LinkedList для этого приёма — ловушка: он двусвязный, у концов всё O(1), но get(i) в середину идёт по ссылкам от края, то есть O(N). Цикл «два указателя по индексам» на нём молча превращается из O(N) в O(N²), хотя код выглядит буква в букву тем же. Подробнее про сам класс — в статье о связных списках.

Окну переменной ширины нужна ещё и память о том, что сейчас внутри окна. Тут берут HashMap или HashSet: доступ по ключу в среднем O(1), и общая оценка прохода не портится. Если ключи — символы или небольшие числа, вместо хеш-таблицы часто заводят простой массив-счётчик на 128 или 256 ячеек — тот же O(1), но без хеширования и упаковки в объекты.

Грабля живёт в попутных указателях «на месте». Соблазн сделать то же самое в ArrayList через remove(i) в цикле кончается плохо дважды. Во-первых, каждое удаление сдвигает весь хвост — это O(N) на операцию и O(N²) на проходе, ровно то, от чего мы уходили. Во-вторых, после удаления следующий элемент занимает освободившийся индекс, а счётчик цикла уже уехал вперёд — и этот элемент просто не проверяется, часть повторов остаётся в списке. Ошибка тихая: список стал короче, результат выглядит правдоподобно. Поэтому чистку и делают перезаписью: set(write, значение) не двигает ничего, а лишний хвост в конце отрезают одним subList(write, size()).clear(). А когда условие удаления это просто предикат по элементу, всё это уже написано: list.removeIf(x -> x < 0) делает ровно такую перезапись внутри за O(N) и остаётся самым коротким правильным способом удалить по условию из ArrayList.

Массив в Go — это срез. Внутри у него обычный массив, который подменяется на больший, когда места перестаёт хватать. Поэтому s[i] стоит O(1), append в конец — O(1) амортизированно (редкий дорогой переезд размазывается по всем добавлениям), а вставка и удаление в середине через slices.Insert и slices.Delete — O(N): соседей приходится сдвигать.

Указателям нужен ровно доступ по индексу за O(1), так что по срезу они бегают с полной скоростью. Ловушка здесь — container/list: у концов всё O(1), но «i-й элемент» в нём это прогулка по ссылкам от края, O(N), и цикл «два указателя по индексам» на нём молча превращается из O(N) в O(N²). Вторая ловушка — строки: feed[i] даёт байт, а не символ, и на кириллице указатели по индексам режут символы пополам. Для текста не из ASCII строку сначала переводят в []rune, и дальше всё как с массивом. Подробнее про устройство списка — в статье о связных списках.

Окну переменной ширины нужна ещё и память о том, что сейчас внутри окна. Тут берут map: доступ по ключу в среднем O(1), и общая оценка прохода не портится. Если ключи — байты или небольшие числа, вместо map часто заводят массив-счётчик [256]int: тот же O(1), но без хеширования, и он лежит на стеке.

Грабля живёт в попутных указателях «на месте». Соблазн сделать то же самое через slices.Delete(s, i, i+1) в цикле по индексу кончается плохо дважды. Во-первых, каждое удаление сдвигает весь хвост — это O(N) на операцию и O(N²) на проходе, ровно то, от чего мы уходили. Во-вторых, после удаления следующий элемент занимает освободившийся индекс, а счётчик цикла уже уехал вперёд — и этот элемент просто не проверяется, часть повторов остаётся. Ошибка тихая: срез стал короче, результат выглядит правдоподобно. Поэтому чистку и делают перезаписью, как в dedup выше, а хвост отрезают одним s = s[:write+1]. Когда условие удаления это просто предикат по элементу, всё это уже написано: slices.DeleteFunc(s, func(x int) bool { return x < 0 }) делает ровно такую перезапись внутри за O(N), а с Go 1.22 ещё и обнуляет освободившийся хвост, чтобы он не держал память.

Массив в JavaScript — это Array, и пока в нём лежат только числа одного вида, движок V8 хранит его плотно, как настоящий массив. Поэтому a[i] стоит O(1), push в конец — O(1) амортизированно, а splice в середине — O(N): соседей приходится сдвигать. Для больших числовых данных ещё плотнее типизированные массивы Int32Array и Float64Array.

Указателям нужен ровно доступ по индексу за O(1), так что по массиву они бегают с полной скоростью. Ловушек две. Первая — дырявый массив: delete a[i] или запись далеко за конец переводят массив в разреженный режим, где доступ по индексу уже не один шаг. Вторая — строки: feed[i] даёт кодовую единицу UTF-16, а не символ, и на эмодзи или редких иероглифах указатели по индексам режут символ пополам. Для такого текста строку сначала разворачивают в массив символов, [...feed], и дальше всё как с массивом.

Окну переменной ширины нужна ещё и память о том, что сейчас внутри окна. Тут берут Map или Set: доступ по ключу в среднем O(1), и общая оценка прохода не портится. Если ключи — коды символов или небольшие числа, вместо хеш-таблицы часто заводят массив-счётчик new Int32Array(256): тот же O(1), но без хеширования.

Грабля живёт в попутных указателях «на месте». Соблазн сделать то же самое через splice(i, 1) в цикле по индексу кончается плохо дважды. Во-первых, каждое удаление сдвигает весь хвост — это O(N) на операцию и O(N²) на проходе, ровно то, от чего мы уходили. Во-вторых, после удаления следующий элемент занимает освободившийся индекс, а счётчик цикла уже уехал вперёд — и этот элемент просто не проверяется, часть повторов остаётся в массиве. Ошибка тихая: массив стал короче, результат выглядит правдоподобно. Поэтому чистку и делают перезаписью, как в dedup выше, а хвост отрезают одним a.length = write + 1. Когда условие удаления это просто предикат по элементу, всё это уже написано: a.filter((x) => x >= 0) делает такой проход за O(N), только возвращает новый массив, а не правит старый; на месте то же самое делает цикл с указателем записи.

Массив в Python — это list. Внутри у него обычный массив ссылок, который подменяется на больший, когда места перестаёт хватать. Поэтому a[i] стоит O(1), append в конец — O(1) амортизированно, а insert и del a[i] в середине — O(N): соседей приходится сдвигать. Строка для указателей тоже годится: feed[i] это символ, а не байт, и стоит O(1), потому что интерпретатор хранит строку с фиксированной шириной символа.

Указателям нужен ровно доступ по индексу за O(1), так что по списку и строке они бегают с полной скоростью. Ловушка здесь — collections.deque: у концов всё O(1), но d[i] в середину идёт по блокам от края, O(N), и цикл «два указателя по индексам» на нём молча превращается из O(N) в O(N²). Дек хорош для окна фиксированной ширины, где нужны только концы, deque(maxlen=k) сам выталкивает вышедший элемент; для индексов берут список. Подробнее про устройство дека — в статье о связных списках.

Окну переменной ширины нужна ещё и память о том, что сейчас внутри окна. Тут берут dict или set, а для счётчиков collections.Counter: доступ по ключу в среднем O(1), и общая оценка прохода не портится. Если ключи — байты или небольшие числа, вместо хеш-таблицы часто заводят список-счётчик [0] * 256: тот же O(1), но без хеширования.

Грабля живёт в попутных указателях «на месте». Соблазн сделать то же самое через del a[i] или a.remove(x) в цикле по индексу кончается плохо дважды. Во-первых, каждое удаление сдвигает весь хвост — это O(N) на операцию и O(N²) на проходе, ровно то, от чего мы уходили. Во-вторых, после удаления следующий элемент занимает освободившийся индекс, а range уже уехал вперёд — и этот элемент просто не проверяется, часть повторов остаётся в списке. Ошибка тихая: список стал короче, результат выглядит правдоподобно. Поэтому чистку и делают перезаписью, как в dedup выше, а хвост отрезают одним del a[write + 1:]. Когда условие удаления это просто предикат по элементу, всё это уже написано: [x for x in a if x >= 0] делает такой проход за O(N) и остаётся самым коротким правильным способом, а на месте то же самое даёт присваивание в срез, a[:] = [x for x in a if x >= 0].

Коротко

Два указателя — две подвижные метки вместо двух вложенных циклов; типичный выигрыш O(N²) → O(N) без дополнительной памяти.
Встречные метки идут навстречу и работают только на упорядоченных данных: на каждом шаге отбрасывается заведомо неподходящая часть.
Попутные метки идут в одну сторону с разной скоростью: перезапись на месте, поиск цикла в списке.
Скользящее окно фиксированной ширины правит сумму на краях вместо полного пересчёта.
Окно переменной ширины расширяется правым краем и подтягивается левым при нарушении условия; левый край никогда не движется назад.
Приём узнаётся по словам «отрезок подряд» в условии и по пересчёту почти одного и того же в наивном решении.
Совпадения может не быть: после цикла возвращают «не найдено» или ближайшую пару; тройку ищут, фиксируя первый элемент, за O(N²).
Общий шаблон окна: правый край расширяет, while сжимает левый, пока условие нарушено («не больше K различных»).

Указатели бегают по ArrayList с той же скоростью, что по массиву, а на LinkedList цикл по индексам становится O(N²); удаление по условию из ArrayList это removeIf, а не remove(i) в цикле.

Указатели бегают по срезу, на container/list цикл по индексам становится O(N²); строку не из ASCII перед указателями переводят в []rune; удаление по условию это slices.DeleteFunc, а не slices.Delete в цикле.

Указатели бегают по плотному массиву, дырки его замедляют; строки с эмодзи разворачивают в [...s]; удаление по условию это filter или указатель записи, splice в цикле квадратичен и пропускает элементы.

Указатели бегают по list и str, на deque цикл по индексам становится O(N²); удаление по условию это включение списка или a[:] = [...], а не del a[i] в цикле.

Что почитать дальше

Префиксные суммы — что делать с суммой на отрезке, когда окно не скользит, а границы произвольны.
Хеш-таблицы — запасной план, когда данные не отсортированы и встречные метки не работают.
Монотонный стек — соседний приём одного прохода: ближайший больший элемент без вложенных циклов.
Двоичный поиск по ответу — ещё один способ снести переборный цикл, когда ответ монотонен.