滑动窗口

无重复字符的最长子串 (opens new window)

var lengthOfLongestSubstring = function (s) {
  let res = 0
  let left = 0
  let right = 0
  const window = {}
  while (right < s.length) {
    // 获取字符串
    const a = s[right]
    // 增大右侧窗口
    right++
    // 字符串在窗口中的数量 默认给1
    window[a] = window[a] ? window[a] + 1 : 1
    // 如果大于 1 了 表明重复了 需要删除掉
    // 保证子串不重复
    while (window[a] > 1) {
      const d = s[left]
      left++
      window[d]--
    }
    res = Math.max(res, right - left)
  }
  return res
}

// 1.  构造 needs window 确定需要的条件

var minWindow = function (s, t) {
  const needs = {}
  const window = {}

  for (let i = 0; i < t.length; i++) {
    const c = t[i]
    if (needs[c] === undefined) {
      needs[c] = 0
    }
    needs[c]++
    window[c] = 0
  }

  const needsSize = Object.keys(needs).length // 不重复字母个数
  //  临时记录子串左右边界
  let left = 0
  let right = 0

  // 窗口内有效值 needs和window 数量和字段一直 就 ++
  let valid = 0
  // 子串长度和起始点  最后求出长度
  let length = Infinity
  let start = 0

  while (right < s.length) {
    const c = s[right]
    right++

    // 计算窗口内的数据
    if (needs[c] !== undefined) {
      window[c]++
      if (window[c] === needs[c]) {
        valid++
      }
    }

    // 判断左侧是否要缩小
    while (valid !== needsSize) {
      // 先判断是否越界
      if (right - left < length) {
        start = left
        length = right - left
      }

      const c = s[left]

      left++
      if (needs[c] !== undefined) {
        if (window[c] === needs[c]) {
          valid--
        }
        window[c]--
      }
    }
  }
  return length === Infinity ? '' : s.substr(start, length)
}

长度最小的子数组 (opens new window)

var minSubArrayLen = function (target, nums) {
  let left = 0
  let result = Infinity
  let sum = 0
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]
    while (sum >= target) {
      result = Math.min(result, i - left + 1)
      sum -= nums[left]
      left++
    }
  }
  return result === Infinity ? 0 : result
}