Two pointers и Sliding Window

Two pointers и Sliding window — это не отдельные алгоритмы, а способы оптимизации перебора, которые снижают сложность с O(n²) до O(n) за счёт умного движения указателей, избегающего лишних пересчётов. Представьте, что вы ищете пару чисел с суммой K в отсортированном массиве. Наивный подход — два вложенных цикла O(n²). Two pointers: ставим указатели на начало и конец, если сумма меньше K — двигаем левый вправо (увеличиваем сумму), если больше — правый влево (уменьшаем). Каждый указатель движется максимум n раз → O(n). Ключ: монотонность — движение указателя в одну сторону гарантированно изменяет условие в нужную сторону.

Two pointers применяется в трёх основных паттернах: (1) Сходящиеся указатели — l и r идут навстречу друг другу (Two Sum Sorted, Container With Most Water, Trapping Rain Water). (2) Быстрый и медленный — fast идёт быстрее slow (Find Middle, Detect Cycle, Remove Duplicates in-place). (3) Два массива — указатели в разных массивах/строках (Merge Sorted Arrays, Is Subsequence). Общий признак: есть упорядоченность (сортировка или монотонность условия), позволяющая безопасно двигать указатели без возврата.

Когда применять / Мотивация

Two pointers применяется в трёх основных паттернах: (1) Сходящиеся указатели — l и r идут навстречу друг другу (Two Sum Sorted, Container With Most Water, Trapping Rain Water). (2) Быстрый и медленный — fast идёт быстрее slow (Find Middle, Detect Cycle, Remove Duplicates in-place). (3) Два массива — указатели в разных массивах/строках (Merge Sorted Arrays, Is Subsequence). Общий признак: есть упорядоченность (сортировка или монотонность условия), позволяющая безопасно двигать указатели без возврата.

Идея / Как работает

Sliding Window — частный случай two pointers: оба указателя двигаются только вправо, образуя “окно” [left, right]. Окно расширяется (right++), когда условие позволяет, и сжимается (left++), когда условие нарушено. Ключевая идея: каждый элемент входит в окно ровно один раз (при right++) и выходит ровно один раз (при left++), поэтому амортизированная сложность O(n). Паттерны: (1) Фиксированное окно — размер k (Max Sum Subarray of Size K, Moving Average). (2) Переменное окно — окно растёт/сжимается под условие (Longest Substring Without Repeating, Minimum Window Substring). (3) Подсчёт подмассивов — количество подмассивов с условием (Subarrays with Sum <= K для положительных чисел).

Когда применять: Сигналы для Two Pointers — “отсортированный массив”, “пара с суммой/произведением”, “in-place модификация с O(1) памятью”, “find duplicates/palindrome”. Для Sliding Window — “подстрока/подмассив с условием”, “максимальная/минимальная длина”, “количество подмассивов”, “все анаграммы/перестановки”. Условие должно быть монотонным: если окно [l, r] не удовлетворяет условию (например, сумма > K), то [l, r+1] тоже не удовлетворяет → можно двигать l, не теряя решений.

Реализация

Задача: Longest Substring Without Repeating Characters (LeetCode 3). Найти длину самой длинной подстроки строки s без повторяющихся символов. Например, “abcabcbb” → 3 (“abc”), “bbbbb” → 1 (“b”), “pwwkew” → 3 (“wke”).

Подход: Это классическая задача на Sliding Window с переменным размером. Используем два указателя left и right (оба стартуют с 0) и Map для хранения последнего индекса каждого символа. Расширяем окно вправо (right++), добавляя s[right] в Map. Если s[right] уже встречался и его последний индекс >= left (то есть он внутри текущего окна), двигаем left на позицию map.get(s[right]) + 1 (исключаем дубликат и всё до него из окна). Обновляем map.set(s[right], right) и максимальную длину max(ans, right - left + 1). Ключевой момент: left движется только вперёд (не откатывается), это гарантирует O(n) — каждый элемент входит и выходит из окна один раз.

function lengthOfLongestSubstring(s) {
    const lastSeen = new Map();
    let left = 0;
    let maxLen = 0;

    for (let right = 0; right < s.length; right++) {
      const char = s[right];

      // Если символ уже был в текущем окне
      if (lastSeen.has(char) && lastSeen.get(char) >= left) {
        // Сдвигаем left за позицию дубликата
        left = lastSeen.get(char) + 1;
      }

      lastSeen.set(char, right);
      maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
  }

  // Two Pointers: Container With Most Water (LeetCode 11)
  function maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxWater = 0;

    while (left < right) {
      const width = right - left;
      const h = Math.min(height[left], height[right]);
      maxWater = Math.max(maxWater, width * h);

      // Двигаем указатель с меньшей высотой
      // Логика: area ограничена min(h[l], h[r])
      // Двигая указатель с большей высотой, мы уменьшаем width,
      // но min высоты может только уменьшиться или остаться → area уменьшится
      // Двигая указатель с меньшей высотой, есть шанс найти бОльшую высоту
      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }

    return maxWater;
  }

  // Two Pointers: 3Sum (LeetCode 15)
  function threeSum(nums) {
    nums.sort((a, b) => a - b); // O(n log n)
    const result = [];

    for (let i = 0; i < nums.length - 2; i++) {
      // Пропускаем дубликаты для первого элемента
      if (i > 0 && nums[i] === nums[i - 1]) continue;

      // Теперь задача сводится к Two Sum для target = -nums[i]
      let left = i + 1;
      let right = nums.length - 1;
      const target = -nums[i];

      while (left < right) {
        const sum = nums[left] + nums[right];

        if (sum === target) {
          result.push([nums[i], nums[left], nums[right]]);

          // Пропускаем дубликаты для второго и третьего элементов
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;

          left++;
          right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }

    return result;
  }

  // Sliding Window: Minimum Window Substring (LeetCode 76)
  function minWindow(s, t) {
    if (t.length > s.length) return "";

    const need = new Map();
    for (const char of t) {
      need.set(char, (need.get(char) || 0) + 1);
    }

    const window = new Map();
    let left = 0;
    let minLen = Infinity;
    let minStart = 0;
    let matched = 0; // количество символов из t, которые полностью удовлетворены в окне

    for (let right = 0; right < s.length; right++) {
      const charR = s[right];

      // Расширяем окно
      if (need.has(charR)) {
        window.set(charR, (window.get(charR) || 0) + 1);
        if (window.get(charR) === need.get(charR)) {
          matched++;
        }
      }

      // Сжимаем окно, пока оно валидно
      while (matched === need.size) {
        // Обновляем минимальное окно
        if (right - left + 1 < minLen) {
          minLen = right - left + 1;
          minStart = left;
        }

        const charL = s[left];
        if (need.has(charL)) {
          if (window.get(charL) === need.get(charL)) {
            matched--;
          }
          window.set(charL, window.get(charL) - 1);
        }
        left++;
      }
    }

    return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
  }

  // Демонстрация
  console.log(lengthOfLongestSubstring("abcabcbb")); // 3
  console.log(lengthOfLongestSubstring("bbbbb")); // 1
  console.log(lengthOfLongestSubstring("pwwkew")); // 3
  console.log(maxArea([1,8,6,2,5,4,8,3,7])); // 49
  console.log(threeSum([-1,0,1,2,-1,-4])); // [[-1,-1,2],[-1,0,1]]
  console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"

Трассировка

Трассировка lengthOfLongestSubstring(“abcabcbb”):

  s = "abcabcbb"
  lastSeen = {}, left = 0, maxLen = 0

  right=0, char='a':
    'a' not in lastSeen
    lastSeen = {a: 0}, maxLen = max(0, 0-0+1) = 1
    [a]bcabcbb, left=0, right=0

  right=1, char='b':
    'b' not in lastSeen
    lastSeen = {a:0, b:1}, maxLen = max(1, 1-0+1) = 2
    [ab]cabcbb, left=0, right=1

  right=2, char='c':
    'c' not in lastSeen
    lastSeen = {a:0, b:1, c:2}, maxLen = max(2, 2-0+1) = 3
    [abc]abcbb, left=0, right=2

  right=3, char='a':
    'a' in lastSeen, lastSeen.get('a')=0 >= left=0 → сдвигаем left
    left = 0 + 1 = 1
    lastSeen = {a:3, b:1, c:2}, maxLen = max(3, 3-1+1) = 3
    a[bca]bcbb, left=1, right=3

  right=4, char='b':
    'b' in lastSeen, lastSeen.get('b')=1 >= left=1 → сдвигаем left
    left = 1 + 1 = 2
    lastSeen = {a:3, b:4, c:2}, maxLen = max(3, 4-2+1) = 3
    ab[cab]cbb, left=2, right=4

  right=5, char='c':
    'c' in lastSeen, lastSeen.get('c')=2 >= left=2 → сдвигаем left
    left = 2 + 1 = 3
    lastSeen = {a:3, b:4, c:5}, maxLen = max(3, 5-3+1) = 3
    abc[abc]bb, left=3, right=5

  right=6, char='b':
    'b' in lastSeen, lastSeen.get('b')=4 >= left=3 → сдвигаем left
    left = 4 + 1 = 5
    lastSeen = {a:3, b:6, c:5}, maxLen = max(3, 6-5+1) = 2
    abcab[cb]b, left=5, right=6

  right=7, char='b':
    'b' in lastSeen, lastSeen.get('b')=6 >= left=5 → сдвигаем left
    left = 6 + 1 = 7
    lastSeen = {a:3, b:7, c:5}, maxLen = max(3, 7-7+1) = 1
    abcabcb[b], left=7, right=7

  Результат: maxLen = 3

  Ключевое наблюдение: left никогда не откатывается назад, только вперёд.
  Каждый элемент обработан ровно дважды (один раз right, один раз left) → O(n).

Сложность

Анализ сложности: lengthOfLongestSubstring: Time O(n) — right проходит по всем символам один раз, left тоже может пройти максимум n позиций (суммарно за все итерации). Каждая операция с Map — O(1). Space O(min(n, m)), где m — размер алфавита (для ASCII = 128, для lowercase letters = 26). maxArea: Time O(n) — каждый указатель двигается максимум n раз. Space O(1). threeSum: Time O(n²) — внешний цикл O(n), внутренний two pointers O(n). Сортировка O(n log n), доминирует O(n²). Space O(1) если не считать результат (или O(n) для сортировки в некоторых реализациях). minWindow: Time O(n + m), где n = s.length, m = t.length — right проходит n, left проходит n, построение need — m. Space O(m) для Map’ов.

Частые ошибки на интервью: (1) Забыть, что Two Pointers на неотсортированных данных не работает — если нужна сумма, либо сортируем O(n log n), либо используем хеш-таблицу O(n). (2) В Sliding Window с Map/Set забыть обновлять счётчики при сдвиге left — частая ошибка в Minimum Window Substring. (3) Неправильный инвариант окна: окно [l, r] должно всегда удовлетворять условию, или всегда нарушать? Выбери одно и следуй. (4) Off-by-one в длине окна: длина = r - l + 1 (если оба указателя на элементах), или r - l (если r указывает за последний). (5) Забыть обработать край массива после цикла — например, в 3Sum после двух указателей нужно пропустить дубликаты.

Типичные ошибки и подводные камни

(1) “Почему в Container With Most Water двигаем указатель с меньшей высотой?” — Если двигаем указатель с большей высотой, width уменьшается, а min(h[l], h[r]) может только уменьшиться (или остаться) → area гарантированно не улучшится. Двигая меньший, есть шанс найти бОльшую высоту. (2) “Как решить 3Sum без сортировки?” — Нельзя за O(n²). С хеш-таблицей можно за O(n²) по времени и O(n) по памяти, но сложно избежать дубликатов (нужны хитрые проверки на уникальность троек). Сортировка проще и стандартна. (3) “Sliding Window для Longest Substring with At Most K Distinct Characters?” — Map для подсчёта частот в окне, переменная distinctCount. Расширяем right, если новый символ → distinctCount++. Если distinctCount > k, сжимаем left, пока distinctCount <= k (уменьшая частоты и проверяя, когда частота станет 0 → distinctCount—). (4) “Prefix Sum vs Sliding Window для Subarray Sum Equals K?” — Sliding Window работает только для положительных чисел (монотонность: увеличивая окно, сумма растёт). Для произвольных чисел (включая отрицательные) — Prefix Sum + HashMap: сохраняем суммы префиксов, для каждой позиции ищем prefixSum - k в HashMap. (5) “Trapping Rain Water — two pointers или DP?” — Оба O(n), но two pointers — O(1) памяти. Идея: держим maxLeft и maxRight, двигаем указатель со стороны меньшего max, вода в текущей позиции = min(maxLeft, maxRight) - height[i].

Follow-up вопросы интервьюера

1. Как модифицировать Longest Substring для “at most 2 distinct characters”? — Используем Map для подсчёта символов в окне. Расширяем right, добавляя s[right] в Map. Если Map.size > 2, сжимаем left: уменьшаем частоту s[left], если стала 0 — удаляем из Map, left++. Повторяем, пока Map.size <= 2. Обновляем maxLen на каждом шаге. Сложность O(n).
2. Find All Anagrams in a String — как эффективно? — Sliding Window фиксированного размера p.length. Два Map: need для p, window для текущего окна. Расширяем окно до размера p.length, затем двигаем окно: добавляем s[right], удаляем s[left], сравниваем window и need (можно оптимизировать: держать счётчик matched символов, сравнивать matched === need.size). O(n) время, O(1) память (26 букв макс).
3. Max Consecutive Ones III — заменить до k нулей, найти макс длину единиц. — Sliding Window: расширяем right, если встретили 0 → zeroCount++. Если zeroCount > k, сжимаем left, пока zeroCount <= k (если s[left] == 0 → zeroCount—). Обновляем maxLen = max(maxLen, right - left + 1). O(n).
4. Sort Colors (Dutch National Flag) — как за O(n) и O(1)? — Three pointers: low (граница 0), mid (текущий), high (граница 2). Инвариант: [0..low-1] = 0, [low..mid-1] = 1, [high+1..n-1] = 2. Если nums[mid] == 0 → swap(mid, low), low++, mid++. Если nums[mid] == 1 → mid++. Если nums[mid] == 2 → swap(mid, high), high— (mid не двигаем, так как не знаем, что пришло слева). O(n) одним проходом.
5. Remove Duplicates from Sorted Array in-place — как? — Two pointers: slow (позиция уникального элемента), fast (исследователь). Если nums[fast] != nums[slow] → slow++, nums[slow] = nums[fast]. В конце первые slow+1 элементов уникальны. O(n) время, O(1) память.
6. Minimum Size Subarray Sum >= target (положительные числа) — как? — Sliding Window: расширяем right, добавляя в сумму. Если sum >= target, пытаемся сжать left, пока sum >= target, обновляя minLen. O(n) — каждый элемент входит/выходит один раз. Если числа могут быть отрицательными, Sliding Window не работает (нужен Prefix Sum или другой подход).

Чеклист на собес

• Узнаю two pointers по сигналам: «отсортированный массив», «найти пару/тройку», «in-place модификация».
• Узнаю sliding window по сигналам: «подмассив/подстрока с условием», «не более K различных», «максимальная длина».
• Различаю два варианта: указатели с разных концов (sum=target) и с одного конца (fast/slow).
• Для sliding window держу инвариант окна и решаю: фиксированный размер или динамический.
• При расширении окна — обновляю состояние и проверяю условие; при сжатии — двигаю left, корректируя состояние.
• Использую Map/Set для быстрой проверки условия (число различных, частоты, существование).
• Сложность всегда O(n) — каждый указатель проходит массив максимум один раз.