从五道leetcode掌握滑动窗口

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
复制代码

var lengthOfLongestSubstring = function(s) {
  const Len = s.length
  let ans = 0
  let left = 0
  // 利用集合来存储窗口数据
  const set = new Set()
  // i实际就是我们的右指针
  for (let i = 0; i < Len; i++) {
    if (Len - left < ans) break
    const code = s[i]
    // 当新元素已经存在窗口中则收缩左指针
    while(set.has(code)) {
      set.delete(s[left])
      left++
    }
    set.add(code)
    ans = Math.max(ans, i - left + 1)
  }
  return ans
};
复制代码

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
复制代码

var checkInclusion = function(s1, s2) {
  // 题目给出的一个特殊条件是全小写字母
  // 所以可以很巧妙的运用长度为26的数组来记录字符出现次数
  const cnt1 = new Array(26).fill(0)
  const cnt2 = new Array(26).fill(0)
  // 利用和字符a的字符差来放入和获取某个字符出现次数
  const charCodeAtA = 'a'.charCodeAt()
  const s1n = s1.length;
  let ans = false;
  if (s2.length < s1.length) return false
  for (let i = 0; i < s1n; i++) {
    cnt1[s1[i].charCodeAt() - charCodeAtA]++
    cnt2[s2[i].charCodeAt() - charCodeAtA]++
  }
  if (cnt1.toString() === cnt2.toString()) return true
  for (let i = s1n, len = s2.length; i < len; i++) {
    // 滑动窗口
    cnt2[s2[i].charCodeAt() - charCodeAtA]++
    cnt2[s2[i-s1n].charCodeAt() - charCodeAtA]--
    // 通过toString来对比是否相等
    if (cnt1.toString() === cnt2.toString()) {
      ans = true
      break
    }
  }
  return ans
};
复制代码

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
复制代码

var findAnagrams = function(s, p) {
  const PLen = p.length
  const countP = new Array(26).fill(0)
  const countS = new Array(26).fill(0)
  const charCodeA = 'a'.charCodeAt()
  const ans = []
  let left = 0
  for (let i = 0; i < PLen; i++) {
    countP[p[i].charCodeAt() - charCodeA]++
  }
  // 滑动窗口
  for (let i = 0, len = s.length; i < len; i++) {
    countS[s[i].charCodeAt() - charCodeA]++
    if (i < PLen - 1) {
      continue
    }
    if (i >= PLen) {
      countS[s[left].charCodeAt() - charCodeA]--
      left++
    }
    // 利用26位数组来对比
    if (countS.toString() === countP.toString()) {
      ans.push(left)
    }
  }
  return ans
};
复制代码

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
复制代码

var numSubarrayProductLessThanK = function(nums, k) {
  const Len = nums.length
  let count = 0
  let left = 0
  let multi = 1
  // 滑动窗口
  for (let i = 0; i < Len; i++) {
    multi = multi * nums[i]
    // 左指针右移动
    while(multi >= k && left <= i) {
      multi = multi / nums[left++]
    }
    count += (i - left + 1)
  }
  return count
};
复制代码

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
复制代码

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