209. Minimum Size Subarray Sum

Задача

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

Примеры

Пример 1

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

Пояснение

Подмассив [4,3] имеет минимальную длину при заданном условии.

Пример 2

Input: target = 4, nums = [1,4,4]
Output: 1

Пример 3

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Решение

Решение

/**
 * Подход: Скользящее окно (two pointers)
 * - Расширяем окно вправо (right++), добавляя элементы в sum
 * - Когда sum >= target, сжимаем окно слева (left++), обновляя минимум
 * - Работает за O(n), т.к. оба указателя проходят массив по разу
 * 
 * Временная сложность: O(n) - каждый элемент обрабатывается максимум 2 раза
 * Пространственная сложность: O(1) - используем только переменные
 */
var minSubArrayLen = function (target, nums) {
  let left = 0;       // левая граница окна
  let sum = 0;        // текущая сумма окна
  let minLen = Infinity;  // минимальная длина
 
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];  // расширяем окно вправо
 
    // сжимаем окно слева, пока sum >= target
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
 
  return minLen === Infinity ? 0 : minLen;
};