В чём разница между указателем сдвига влево и вправо в алгоритме скользящего окна?

Основная идея скользящего окна

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

Разница в поведении

• Правый указатель: всегда движется вперёд на каждой итерации, добавляя элемент в окно. Он отвечает за исследование новых данных.
• Левый указатель: двигается только при необходимости, когда нужно уменьшить окно (например, сумма превысила лимит). Он сдвигается вправо, удаляя крайний левый элемент.

Пример кода

function maxSumSubarray(arr, k) {
  let left = 0, sum = 0, maxSum = 0;
  for (let right = 0; right < arr.length; right++) {
    sum += arr[right]; // правый расширяет окно
    if (right >= k - 1) {
      maxSum = Math.max(maxSum, sum);
      sum -= arr[left]; // левый сужает окно
      left++;
    }
  }
  return maxSum;
}

В этом примере правый указатель добавляет каждый элемент, а левый удаляет элемент, когда окно достигает размера k.

Вывод

Правый указатель всегда движется вперёд, расширяя окно, а левый — только по условию, сужая окно. Это позволяет эффективно решать задачи с подмассивами за O(n) времени.