Паттерны решения задач в JavaScript: sliding window, two pointers

Две трети задач на массивы на собеседованиях решаются двумя паттернами: sliding window и two pointers. Если вы их освоите — большинство задач будет сводиться к распознаванию «а, это sliding window» и написанию 15 строк кода.

Разбираем оба паттерна: когда использовать, как реализовать и на каких задачах тренироваться.

Sliding window

Суть

Массив или строка — окно фиксированной или переменной длины «едет» по ним, и на каждом шаге мы обновляем результат. Вместо вложенных циклов — один проход, O(n).

Когда использовать

• Максимальная/минимальная сумма подмассива фиксированной длины
• Максимальная длина подмассива с условием
• Подсчёт подстрок с уникальными символами

Шаблон

function slidingWindow(arr, k) {
  let windowSum = 0;
  let maxSum = -Infinity;

  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];

    if (i >= k) {
      windowSum -= arr[i - k];
    }

    if (i >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
    }
  }

  return maxSum;
}

Задача 1: Максимальная сумма подмассива фиксированной длины

Дан массив nums и число k. Найдите максимальную сумму подмассива длины k.

function maxSumSubarray(nums, k) {
  let windowSum = 0;

  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let maxSum = windowSum;

  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

maxSumSubarray([2, 1, 5, 1, 3, 2], 3); // 9 (подмассив [5, 1, 3])

Сложность: O(n) время, O(1) память.

Задача 2: Длина самого длинного подмассива с суммой ≤ target

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

function longestSubarray(nums, target) {
  let windowSum = 0;
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < nums.length; right++) {
    windowSum += nums[right];

    while (windowSum > target) {
      windowSum -= nums[left];
      left++;
    }

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

  return maxLen;
}

longestSubarray([3, 1, 2, 7, 4, 2, 1, 1, 5], 8); // 4

Внутренний while сдвигает левую границу, пока условие не выполнится. Это variable-size sliding window — длина окна меняется.

Задача 3: Максимальное количество единиц после замены нулей

Дан массив из 0 и 1 и число k — максимальное количество нулей, которое можно заменить на единицы. Найдите длину самого длинного подмассива единиц.

function longestOnes(nums, k) {
  let left = 0;
  let zeros = 0;
  let maxLen = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++;

    while (zeros > k) {
      if (nums[left] === 0) zeros--;
      left++;
    }

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

  return maxLen;
}

longestOnes([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2); // 6

Ключевая идея: окно «допускает» до k нулей. Когда нулей больше — сдвигаем левую границу.

Two pointers

Суть

Два указателя движутся навстречу друг другу или в одном направлении по отсортированному массиву. На каждом шаге — сравнение и решение: сдвинуть левый, правый или оба.

Когда использовать

• Задачи на пары в отсортированном массиве
• Палиндромы и сравнение с концов
• Слияние отсортированных массивов

Шаблон

function twoPointers(arr) {
  let left = 0;
  let right = arr.length - 1;

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

    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }

  return [-1, -1];
}

Задача 4: Два числа с заданной суммой

Дан отсортированный массив nums и число target. Найдите индексы двух элементов, сумма которых равна target.

function twoSumSorted(nums, target) {
  let left = 0;
  let right = nums.length - 1;

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

    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }

  return [-1, -1];
}

twoSumSorted([2, 7, 11, 15], 9); // [0, 1]
twoSumSorted([1, 2, 3, 4, 6], 6); // [1, 3]

Сложность: O(n) время, O(1) память. Вместо хэш-таблицы — просто два указателя.

Задача 5: Палиндром (проверка)

Проверьте, является ли строка палиндромом, учитывая только буквы и цифры.

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    while (left < right && !/[a-z0-9]/i.test(s[left])) left++;
    while (left < right && !/[a-z0-9]/i.test(s[right])) right--;

    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;

    left++;
    right--;
  }

  return true;
}

isPalindrome("A man, a plan, a canal: Panama"); // true
isPalindrome("race a car"); // false

Указатели прыгают через не-алфавитные символы и сравнивают по краям к центру.

Задача 6: Удаление дубликатов из отсортированного массива

Удалите дубликаты на месте. Верните количество уникальных элементов.

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;

  let slow = 0;

  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }

  return slow + 1;
}

removeDuplicates([1, 1, 2, 3, 3]); // 3, массив → [1, 2, 3, ...]

Здесь два указателя движутся в одном направлении: fast ищет новые элементы, slow записывает их на позицию|unique.

Комбинированные задачи

Задача 7: Подстрока без повторяющихся символов

Найдите длину самой длинной подстроки без повторяющихся символов.

function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }

    seen.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

lengthOfLongestSubstring("abcabcbb"); // 3
lengthOfLongestSubstring("bbbbb"); // 1

Это sliding window + hash set. Окно расширяется вправо, сжимается слева при повторе.

Задача 8: Слияние двух отсортированных массивов

function merge(nums1, m, nums2, n) {
  let i = m - 1;
  let j = n - 1;
  let k = m + n - 1;

  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k--] = nums1[i--];
    } else {
      nums1[k--] = nums2[j--];
    }
  }

  while (j >= 0) {
    nums1[k--] = nums2[j--];
  }

  return nums1;
}

merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3); // [1, 2, 2, 3, 5, 6]

Два указателя идут с конца обоих массивов, записывая в конец nums1.

Как выбрать паттерн

Где тренироваться

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

Попробуйте решить задачи на Девстанции — здесь есть десятки задач, которые тренируют sliding window и two pointers. AI проверит ваш код и подскажет, если есть более эффективное решение.

А если готовитесь к собеседованию — посмотрите чеклист из 50 вопросов и план подготовки за неделю.