滑动窗口刷题模板

以下例子，用于获取数组中满足队列只和大于目标数字的长度最小的子数组

关键在于「快指针」和「慢指针」，嵌套 2 个 while，快指针不停地向终点移动，一旦满足要求，则进入内部循环开始移动慢指针。

const minSubArrayLen = function (target, nums) {
  let result = Infinity
  let sum = 0
  let slow = 0,
    fast = 0
  while (fast < nums.length) {
    sum += nums[fast]
    while (sum >= target) {
      // 记录，注意计算数组长度需要索引差值+1
      result = Math.min(result, fast - slow + 1)
      // 减去左边值，收缩范围
      sum -= nums[slow]
      slow++
    }
    fast++
  }
  return result === Infinity ? 0 : result
}

const minSubArrayLen = function (target, nums) {
  let result = Infinity
  let sum = 0
  let slow = 0,
    fast = 0
  while (fast < nums.length) {
    sum += nums[fast]
    while (sum >= target) {
      // 记录，注意计算数组长度需要索引差值+1
      result = Math.min(result, fast - slow + 1)
      // 减去左边值，收缩范围
      sum -= nums[slow]
      slow++
    }
    fast++
  }
  return result === Infinity ? 0 : result
}

// 求不重复的最长子字符串
var lengthOfLongestSubstring = function (s) {
  let i = 0
  let ans = 0
  let arr = s.split('')
  let tmpl = []
  while (i < arr.length) {
    let nextChar = arr[i]
    // 如果下一个字符和已有的重复了，收缩左边界到不重复为止
    while (tmpl.includes(nextChar)) {
      tmpl.shift()
    }
    // 字符串进队列
    tmpl.push(nextChar)
    // 记录长度
    ans = Math.max(ans, tmpl.length)
    // 继续扩充右边界
    i++
  }
  return ans
}

// 求不重复的最长子字符串
var lengthOfLongestSubstring = function (s) {
  let i = 0
  let ans = 0
  let arr = s.split('')
  let tmpl = []
  while (i < arr.length) {
    let nextChar = arr[i]
    // 如果下一个字符和已有的重复了，收缩左边界到不重复为止
    while (tmpl.includes(nextChar)) {
      tmpl.shift()
    }
    // 字符串进队列
    tmpl.push(nextChar)
    // 记录长度
    ans = Math.max(ans, tmpl.length)
    // 继续扩充右边界
    i++
  }
  return ans
}

滑动窗口刷题模板 ​

滑动窗口刷题模板