滑动窗口

滑动窗口本质也是双指针，用 left 和 right 维护一个连续区间。

固定窗口

窗口长度固定，比如长度为 k 的子数组。

先让右边进窗口，窗口超过 k 后，再让左边出窗口。

let sum = 0
let res = 0

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

  if (right >= k) {
    sum -= nums[right - k]
  }

  if (right >= k - 1) {
    res = Math.max(res, sum)
  }
}

643. 子数组最大平均数 I

固定长度为 k，最大平均数就是最大窗口和除以 k。

function findMaxAverage(nums: number[], k: number): number {
  let sum = 0
  let max = -Infinity

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

    if (right >= k) {
      sum -= nums[right - k]
    }

    if (right >= k - 1) {
      max = Math.max(max, sum)
    }
  }

  return max / k
}

分离窗口（可变窗口）

左右指针分开移动，窗口长度不固定。

通常是右指针不断扩大窗口，当窗口不满足条件时，再移动左指针缩小窗口。

let left = 0

for (let right = 0; right < nums.length; right++) {
  // nums[right] 进窗口

  while (窗口不满足条件) {
    // nums[left] 出窗口
    left++
  }

  // 更新答案
}

3. 无重复字符的最长子串

窗口内不能有重复字符，有重复就不断移动左指针。

function lengthOfLongestSubstring(s: string): number {
  const set = new Set<string>()
  let left = 0
  let res = 0

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

    set.add(s[right])
    res = Math.max(res, right - left + 1)
  }

  return res
}

209. 长度最小的子数组

窗口和大于等于 target 后，尝试缩小窗口。

function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0
  let sum = 0
  let res = Infinity

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

    while (sum >= target) {
      res = Math.min(res, right - left + 1)
      sum -= nums[left]
      left++
    }
  }

  return res === Infinity ? 0 : res
}