关于leetcode:前端刷完这12道滑动窗口就可以出山面试了

前言

常常会有人问，作为前端，你在理论工作中用到过哪些算法，之前我答复是，树和位运算，而最近在学习网络模块，发现了和前端，起码是和网络相干的一种算法，那就是 滑动窗口；

咱们晓得在 HTTP1.1 发送申请，TCP 会将申请传输到服务端，而对于 TCP 协定，最重要的能力之一就是管制流速；

当发送方须要发送很多申请的时候，这些申请会阻塞在某一个缓存中期待 TCP 发送，这个前面还有源源不断的申请发动，那总不能一下子全堵在缓存上吧，会炸掉的，这个时候这个模型就是滑动窗口了

发送过程有三个状态：

• 绿色是发送并连贯胜利的
• 浅绿色是发送，然而还没有收到 ACK 响应的，这个时候有可能会挂掉，所以这个时候发送方还得存着这个申请随时筹备重发
• 红色是期待发送的
• 前面那些就是被阻塞的申请了

这个时候 TCP 可能缓存的申请数就是一个窗口，每当浅绿色转成深绿色，那么窗口就能够像左边滑动，而窗口还保留的状态仍然能够复用，这就是 滑动窗口 的魅力了

滑动窗口最大特点是，滑动窗口过程中，保留在窗口里的数据状态间接复用，不须要再次构建，节约资源；

那么接下来咱们通过做题来相熟一下滑窗，并看看是否有更多不一样的状况吧；

注释

依据滑窗窗口大小是否固定，分成了两种：固定大小的窗口 和 可变窗口大小;

前言谈及的 TCP 中的滑窗状况，其实是一个固定大小的滑窗，当然也能够先给定局部大小，而后依据流速进行扩大，那是后续的操作了；

而更多的状况是不固定大小的滑窗，这类滑窗个别都是创立过程中，一股脑子将资源耗尽去扩充窗口，达到一个阈值，而后再膨胀窗口，依据具体题目，达到一个均衡了；

这其实就如同是一个疾速试错过程，先将状况推到极致了，而后退出对应的变量来膨胀窗口，找到比拟适合的一个状况，等到合规的状况在窗口里突破了，就从新扩大；

滑窗其实在了解题意的时候，又有点一分为二的感觉，就是我能够将窗口里的状态和窗口外的状态切离开，然而他们又是 此消彼长 的关系，这样一直衡量, 达到一个动态平衡的状态，就是某些题的后果

模板

固定大小的窗口

• l 初始化为 0
• 初始化 r, 使得 r-l+1 就是窗口大小
• 同时挪动 l 和 r
• 判断窗口内的间断元素是否满足题目限定的条件

可变窗口大小

• l r 都初始化为 0
• r 指针挪动一步

• 判断窗口内的间断元素是否满足条件

  • 满足，再判断是否须要更新最优解；如果须要则更新，并尝试通过挪动 l 指针放大窗口的大小
  • 不满足，则持续

双滑窗景象

• 一般的不定滑窗都是先走 r 指针，而后达到触发条件，而后膨胀 l 指针，膨胀到不达标之后进行，而后 r 指针重新启动
• 然而有那么一些题目，当 r 指针达标后, l 指针在一段范畴内 [l1,l2)，且可能与后续的 [r1,r2) 任何两个指针形成的滑窗都会形成合规的滑窗
• 那么这个时候用单个指针 l 膨胀到不符合要求的 l2, 那么就只产生 [l1,l2）与 r1 的条件，而原本应该合规的 lx-rx 都被干掉了(lx 在 [l1,l2] 中)，因为这个时候 l 曾经跑到 l2 处了
• 这个时候就须要开两个指针 l1, l2，每次固定 r 指针的时候，咱们找出第一个符合要求的 l1, 和截止地位 l2, 而后持续让 r 走，挪动过程始终保持两个滑窗 [l1.r],[l2,r]，能够保障在整个挪动过程所有的状况都思考到了
• 这类题目都是求数量，比方说 某种状况的子数组有多少个，这样就得将所有状况都弄出来，然而如果只是要求一个极值，比方说这些符合要求的状况中，最小是多少，那么就没必要用双滑窗了，因为 r 指针的挪动必定会扩充窗口，所以 l 指针只须要保留对应的极值(第一个或者最初一个)，而后求出极值即可

最初

滑窗是双指针的一种非凡状况，咱们在应用双指针解决问题的时候，可能不会思考前一个窗口里的状态值，只是将所有状况都思考进行，这样就会有很多计算是反复的，滑窗就是一种优化了的双指针状况。

所以算法还是有点用的，起码在高级的时候，咱们能够更好的了解咱们应用的工具的内核，而不仅仅只是雾里看花，知其然不知其所以然；

所以加油！！

题目列表

438. 找到字符串中所有字母异位词

@剖析

0. 本题与 209. 长度最小的子数组 思路差不多
1. 这道题窗口就固定为 p 的长度大小了，所以看着是固定窗口大小的题目 — 然而这里用的却是不定窗口的思路，然而窗口长度成了一个限定值，一旦超出限定的窗口大小，就膨胀一次
2. 尽管题目说的是找字幕异位词，然而从理论的例子能够看出，只有是合乎 p 的字符对应的子串就 ok 了，不论得出的 ss 是否和 p 是一样的排列
3. 用 pMap 存储 p 的字符状态，sMap 用来存储固定窗口的值，用 sMap 中的 valid 变量类型数量和 pMap 中的比对，用来判断是否符合要求
4. 工夫复杂度 O(n)

var findAnagrams = function (s, p) {const pMap = new Map();
  const sMap = new Map();
  let ret = []; // 存储合乎要求的首个字符

  for (let pp of p) {pMap.set(pp, pMap.get(pp) ? pMap.get(pp) + 1 : 1);
  }
  let valid = 0; // 存储合乎 p 的变量
  let l = (r = 0);
  while (r < s.length) {const rr = s[r];
    sMap.set(rr, sMap.get(rr) ? sMap.get(rr) + 1 : 1);
    if (sMap.get(rr) === pMap.get(rr)) {
      // 两个 key 对应的 value 值统一的时候，才会减少 valid
      valid++;
    }
    // 如果加上这个 r 这个字符，长度超出了固定窗口的长度，则须要先膨胀 l, 再断定 
    if (r - l === p.length) {
      // 从进入到这里逻辑开始，其实就是属于固定窗口两侧的指针一起跑，这里是 l 指针开始跑，之前因为还没初始化完窗口
      const ll = s[l];
      if (pMap.get(ll) === sMap.get(ll)) {
        // 如果膨胀过程中的这个值属于 valid 的
        valid--;
      }
      sMap.set(ll, sMap.get(ll) - 1);
      l++;
    }
    if (valid === pMap.size) {
      // 合乎要求
      ret.push(l);
    }
    r++;
  }

  return ret;
};

参考视频：传送门

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

// 3. 无反复字符的最长子串

剖析
1. 这里求的是最长的子串，证实有很多长度不一的子串，那么就是有很多大小不一的窗口，所以属于窗口不固定的滑窗题
2. 初始化 l r，初始化一个 map 用来寄存窗口里的字符的
3. map 是用来做条件判断的，判断窗口扩大过程中是否和已有的窗口字符反复了，如果反复了，那么就要膨胀窗口 s[r]=== s[l] 而后 l++, 
4. 而后不论是否整顿窗口，r 指针都会持续扩大上来，所以解决完了，须要从新加上 s[r]，并持续走上来
5. 工夫复杂度 ${O(n)}$ 因为 r 指针遍历一次，走的过程中遇到反复值，l 指针挪动，最多 l 也就遍历一次，也就是最多直走了 2n
6. 空间复杂度 $(O(k))$ k 是最大的窗口 size
var lengthOfLongestSubstring = function(s) {const map = new Map() // 这个用来寄存
    let l = r = 0 
    let max = 0
    while(r<s.length) {if(map.has(s[r])){
            // 阐明窗口里的值曾经呈现反复了，所以须要整顿窗口
            max = Math.max(max,map.size) // 存一下大小
            // 开始膨胀窗口，找出 s[r] 同值的那个地位
            while(s[l] !== s[r]){map.delete(s[l])
                l++
            }
            // 找到了 -- 再移除一下
            map.delete(s[l])
            l++
        }
        // 将以后 s[r] 字符存起来
        map.set(s[r],1)
        r++
    }
    // 这个时候 r 走到底了，return Math.max(max,map.size)
}

console.log(lengthOfLongestSubstring("aab"))

剖析

1. 依据第一次剖析，发现 map 还有移除操作，感觉不太适合，而且存储的时候也只是存了字符，没有将对应的下标用起来，所以想了上面的改良版
2. 每一次扩充窗口的时候，判断一下 map 是否存在这个 key，同时判断一下对应的 value 值是否大于等于 l 指针 — 这是为了判断是否存在反复字符在以后窗口里，因为当初曾经不删除 map 里的值了，所以要用 value 和 l 的大小进行比拟
3. 如果是窗口里的反复值，那么先存一下以后窗口的最大值，而后将 l 指针跳到反复值的下一个地位，而后更新 s[r] 的地位，持续遍历
4. 如果不是反复值，就失常存储 s[r] 的地位
5. 留神，这里不能用 map.size 来判断窗口大小，因为当初 map 存的是所有遍历的字符的汇合，所以要用 r-l; 因为每次 r 都指向窗口的下一个值，所以间接 r-l, 而不须要 +1
6. 工夫复杂度 O(n), 这一次是值跑一次，l 根本靠跳
7. 空间复杂度 (O(k)) k 是字符窗中不同字符的汇合值

var lengthOfLongestSubstring = function(s) {const map = new Map() // 这个用来寄存窗口呈现过的值
    let l = r = 0 
    let max = 0
    while(r<s.length) {if(map.has(s[r]) && map.get(s[r])>=l){
            // 曾经遍历过了这个值且在以后的这个窗口里
            max = Math.max(max,r-l) // 先存一下大小
           l = map.get(s[r]) +1 // 跳到反复呈现字符后面去了
        }
        // 将以后 s[r] 字符存起来, 并将字符的下标也存起来 -- or 更新一下罪状 s[r] 的地位
        map.set(s[r],r)
        r++
    }
    // 这个时候 r 走到底了，return Math.max(max,r-l)
}

76. 最小笼罩子串

剖析

1. 这里求的是符合要求的最小的子串，所以窗口必定不是固定大小的
2. 这里断定条件关乎于 t 中的字符及数量，也须要 s 的字符和数量做比照，所以须要用到两个 map 进行存储
3. 先把 t 存储到 tMap 中去，而后开始挪动 r 指针扩充的窗口；
4. 当窗口中的某个字符 s[r] 的数量大于等于 tMap 中 s[r] 的数量时，则这个窗口合乎 t 字符串的变量数 valid 加一，始终到 valid 的长度刚好和 tMap 长度一样的时候，就是找到了符合要求的子串了
5. 找到子串后，须要压缩窗口的大小，所以 l 要启动了
6. 只有 s[l] 在 sMap 中的值不低于 tMap 中的值，那么就拼命的压缩；
7. 只有当长度比曾经保存起来的符合要求的子串小的时候，或者初始化的时候，就替换 ret
8. 而后 l 指针持续走一步，对应窗口就会生效，然还持续寻找下一个符合要求的窗口，反复下面的操作
9. 工夫复杂度 O(N), 空间复杂度 O(N)

function minWindow(s, t) {const sMap = new Map();
  const tMap = new Map();

  // 先将 t 存起来
  for (let tt of t) {tMap.set(tt, tMap.get(tt) ? tMap.get(tt) + 1 : 1);
  }
  let ret = "";
  let l = (r = 0); // 不固定的滑窗的初始化
  let valid = 0; // 示意窗口中匹配 t 字符的数量 -- 匹配的字符是指：字符 ss 在窗口里的数量超过了 ss 在 t 字符串中这个字符数量
  while (r < s.length) {const ss = s[r];
    sMap.set(ss, sMap.get(ss) ? sMap.get(ss) + 1 : 1); // 存起来
    if (sMap.get(ss) === tMap.get(ss)) {
      // 证实 ss 曾经匹配了
      valid++;
    }

    if (valid === tMap.size) {
      //   窗口里的字符串曾经齐全匹配了，那么就须要膨胀一下了
      while (sMap.get(s[l]) !== tMap.get(s[l])) {// 因为当初的初始条件是: 对于某个字符 s[l], sMap.get(s[l])>=tMap.get(s[l])
        // 所以能够干掉一些，晓得 === 的时候
        sMap.set(s[l], sMap.get(s[l]) - 1);
        l++;
      }
      if (r - l + 1 < ret.length || !ret.length) {
        // 如果长度更小了，或者初始化的 ret, 那就替换一下吧
        ret = s.slice(l, r + 1);
      }
      //  持续走吧，总得砍掉一个 valid 的，sMap.set(s[l], sMap.get(s[l]) - 1);
      valid--; // 少了一个 s[l] 了
      l++;
    }
    r++;
  }
  return ret;
}

209. 长度最小的子数组

剖析

1. 这里求的是符合要求的间断数组的长度，所以这个长度是不确定，也就是窗口长度不确定；
2. 这里求的是一个窗口累加值 sum >= target, 一旦满足要求就要压缩窗口，失去最小符合要求的间断数组的长度
3. r 指针负责右侧裁减窗口大小，l 指针负责膨胀窗口，失去最优解
4. 工夫复杂度 O(n)

 var minSubArrayLen = function (target, nums) {
    let ret = Infinity;
    let l = (r = 0);
    let sum = 0;
    while (r < nums.length) {sum += nums[r];
      while (sum >= target) {
        // 符合要求，开始压缩窗口大小
        ret = Math.min(ret, r - l + 1); // 更新一下
        sum -= nums[l];
        l++;
      }
      r++
    }
    return ret === Infinity ? 0: ret
  };

904. 水果成篮

剖析

1. 审题，数组中的值代表的类型，比方说 1 型水果，2 型水果；给定两个篮子，也就是最多抉择两种类型的水果放进篮子里，而后保障能进去的树最多，即 r-l+1 的值最大，所以属于窗口不固定的滑动窗口题目
2. 用 map 作为篮子存储水果，map.size 最大应该为 2，
3. 一旦 map.size 值超出 2，证实存储超过了 2 种类型的水果，所以须要膨胀 l，将一些其余类型的果子扔掉，直到 map 中的品种复原到两种;
4. 工夫复杂度 O(n)

 var totalFruit = function(fruits) {const map = new Map() // 篮子，大小为 2，用来存储以后窗口下的水果
    let ret = 0
    let l = r =0 
    while(r < fruits.length){ret = Math.max(ret,r-l); // 先保留一下上一次的大小
        const rr = fruits[r]
        map.set(rr,map.get(rr)?map.get(rr)+1:1)
        // 如果超了，则须要膨胀一整类的树
        while(map.size > 2){
            // 长度超了，向左膨胀
            const ll = fruits[l]
            if(map.get(ll) ===  1){map.delete(ll)
            }else{map.set(ll,map.get(ll)-1)
            }
            l++ 
        }
        r++
    }
    return Math.max(ret,r-l);
};

930. 和雷同的二元子数组

剖析 — 双滑动窗口

1. 不固定大小的滑动窗口，存在两个左指针 l1,l2 , 其中 [l1,r] 的 sum 总是小于等于 goal，而 [l2,r] 总数小于 goal 的
2. 每次固定 r 指针，咱们晓得 [l1,l2-1]的任意一个 [lx,r] 都符合要求
3. 这里用到了两个滑窗进行比拟出值，起因是 nums[i] 只能是 0,1, 所以会呈现间断的符合要求的值，
4. 所以每一次固定 r 指针的时候，[l1,r] 放弃符合要求即值为 goal 的状态，[l2,r] 放弃刚好小于 goal 的状态；
5. 则每一次向右滑动窗口后，都失去两个边缘值的窗口，这样就失去想要求的后果
6. 工夫复杂度为 O(n2)，空间复杂度 O(n) */

 var numSubarraysWithSum = function (nums, goal) {
    let ret = 0
    let l1 = 0, l2 = 0 
    let sum1 = 0,sum2 = 0 // sum1 <= goal, sum2 < goal
    let r = 0
    while(r<nums.length){sum1+=nums[r]
        while(l1<=r && sum1>goal){sum1-=nums[l1]
            l1++
        }
        sum2+=nums[r]
        while(l2<=r && sum2>=goal){sum2-=nums[l2]
            l2++
        }
        ret+= l2-l1
        r++
    }
    return ret
}

剖析 — 双指针

1. 双指针进行匹配
2. 而后每一次固定其中一边，进行求值，
3. 没有复用任何的值，所以工夫复杂度为 O(n2)，空间复杂度 O(n)

var numSubarraysWithSum = function (nums, goal) {
  let ret = 0;
  for (let i = 0; i < nums.length; i++) {
    // 固定 i 指针
    let sum = 0;
    let r = i;
    while (r <= nums.length) {sum += nums[r];
      if (sum === goal) ret++;
      r++;
    }
  }
  return ret;
};

剖析 — 前缀和

1. 用 map 记录 key 为前缀和，value 为有多少前缀和为 key 的子数组
2. 如果以后前缀和 prevSum – goal 失去的值 temp 曾经存在在 map 中，证实有 value 个值 [l,cur] 使得 sum 为 goal
3. 工夫复杂度 O(n), 空间复杂度 O(n)

 var numSubarraysWithSum = function (nums, goal) {const map = new Map()
    let prevSum = 0
    let ret = 0
    for(let num of nums){
        prevSum+=num
        if(map.has(prevSum-goal)){ret+=map.get(prevSum-goal)
        }
        if(prevSum === goal){ret++}
        map.set(prevSum,map.get(prevSum)?map.get(prevSum)+1:1)
    }

    return ret
};

992. K 个不同整数的子数组

剖析

1. 只有品种 map.size === k 的窗口，都是符合要求的，所以窗口大小不固定
2. 遍历 r 指针，并在每次判断时固定 r 指针，设计 l1 指针，使得 [l1,r] 中的品种小于等于 k，设计 l2, 使得 [l2,r] 中的变量小于 k
3. 则每一个固定的 r，中，[l1,l2) 之间的值和后续的 [l2,r] 能够形成变量为 k 的子数组，所以每一次固定 r，最终失去符合要求的数量是 l2-l1
4. 整体思路和 930. 和雷同的二元子数组 一样
5. 只是一个的判断条件是子数组的和，一个是子数组中的品种
6. 这种只求组合数量的题目，都须要关注断定值合规的时候，窗口左右延长都是能够失去适合的值的
7. 工夫复杂度 O(n), 空间复杂度 O(n)

var subarraysWithKDistinct = function (nums, k) {
  let ret = 0;
  const map1 = new Map(); // 用来存储窗口中值和呈现的次数
  const map2 = new Map(); // 用来存储窗口中值和呈现的次数
  let l1 = (l2 = 0);
  let r = 0
  while (r < nums.length) {const rr = nums[r];
    map1.set(rr, map1.get(rr) ? map1.get(rr) + 1 : 1);
    map2.set(rr, map2.get(rr) ? map2.get(rr) + 1 : 1);
    while (map1.size > k) {
      // 窗口的变量曾经超过了 k，所以须要 l 指针膨胀
      const ll = nums[l1];
      l1++;
      if (map1.get(ll) === 1) {map1.delete(ll);
      } else {map1.set(ll, map1.get(ll) - 1);
      }
    }

    while (map2.size >= k) {
        // 窗口的变量曾经超过了 k，所以须要 l 指针膨胀
        const ll = nums[l2];
        l2++;
        if (map2.get(ll) === 1) {map2.delete(ll);
        } else {map2.set(ll, map2.get(ll) - 1);
        }
      }
      ret += l2-l1
    r++;
  }
  return ret;
};

978. 最长湍流子数组

剖析

1. 审题可得，这里能够转换成对于某一个节点 i, 必须满足这个 i 是一个最高点或者最低点
2. 当 l === r 的时候，如果呈现 arr[l] === arr[l + 1], 则先去重
3. 对于不同的 l 和 r，须要对 r 两侧的值进行判断，如是极值，则扩大窗口，如果 r 不是极值, 那么对应的 [l,r+1] 必定也不是了，所以将窗口膨胀到 l = r 的水平，从新再进行窗口的创立
4. 须要留神，为什么 l 膨胀到 r 而不是 r+1, 因为比对 r 是否是极值的时候，须要进行 r-1,r,r+1, 所以 r 和 r+1 的值可能会合乎是后续的 [r,r+x] 的湍流数组，所以 l 膨胀到 r
5. 至于 r 和 r+1 对应的值可能会相等，会在循环的第一次判断中的去重进行解决
6. 本题最难是审题
7. 工夫复杂度 O(n)

var maxTurbulenceSize = function (arr) {
  const len = arr.length;
  let max = 1; // 起码是 1
  let l = 0,
    r = 0; // 来个初始值
  while (r < len - 1) {if (l === r) {
      // 上一次比对不符合要求
      if (arr[l] === arr[l + 1]) {
        //  去重
        l++;
      }
      r++;
    } else {
      // 有和下一个进行比对
      if (arr[r - 1] < arr[r] && arr[r] > arr[r + 1]) {r++;} else if (arr[r - 1] > arr[r] && arr[r] < arr[r + 1]) {r++;} else {
        // 不符合要求
        l = r;
      }
    }

    max = Math.max(max, r - l + 1);
  }
  return max;
};

1004. 最大间断 1 的个数 III

剖析

1. 这里其实用到的是双指针的形式
2. 左右指针造成了一个合乎要求的区域，用 arr 来缓存从 0-1 变更的值
3. 每当应用完变更次数 k 之后，再次遇到 0 的时候，咱们只能先保留以后长度的区域，而后将 l 指针跳转到最小的变更下标，而后再次进行区域的裁减
4. 工夫复杂度 O(n),n 是 nums 的长度；空间复杂度 O(k)

var longestOnes = function (nums, k) {const changeArr = []; // 用 arr 来存储从 0-1 的下标的值
  let l = (r = 0);
  let ret = 0;
  while (r < nums.length) {const rr = nums[r];
    if (k === 0) {
      // 非凡状况，不做任何解决
      if (rr === 0) {ret = Math.max(ret, r - l); // 先保留以后的这个长度
        l = r + 1;
      }
    } else {if (rr === 0 && changeArr.length === k) {
        // 以后值是 0，且曾经变更了 k 次，无奈再变了
        ret = Math.max(ret, r - l); // 先保留以后的这个长度
        // 因为是间断的变动，所以 l 能够间接指向第一个变动值之前
        l = changeArr.shift() + 1;}
      if (rr === 0 && changeArr.length < k) {changeArr.push(r);
      }
    }
    r++;
  }
  return Math.max(ret, r - l);
};
console.log(longestOnes([0, 0, 1, 1, 1, 0, 0], 0));

1234. 替换子串失去均衡字符串

剖析

1. 本题最难的点在于切分好窗口，窗口里的值是待变更的，窗口外的值是曾经确定好的，对应的每一个字符的数量都小于等于 n/4
2. 为什么要这样来初始化窗口，窗口外的值的字符数量小于等于 n/4, 那么就能够变更窗口里的值，使得最终的值合乎均衡字符串，因为窗口的值能够任意变，然而一旦里面某个字符的数量超出 n/4, 而后变更窗口的值，使得最终的数量变少了吧；
3. 先遍历一遍，保留所有字符对应的数量到 map 中，留神，这里要先初始化 QWER，保障 map 中有这 4 个 key
4. 用 valid 示意滑窗外满足字符小于等于 n/4 的数量，边际条件，如果间接满足，返回 0
5. 而后 r 指针滑动扩大窗口，map 会缩小对应字符的数量，当 rr 字符的值达到临界值的时候，valid 会产生变更
6. 当 valid === 4 的时候，示意滑窗外曾经满足要求，只有扭转滑窗长度的字符，就能实现均衡，这个时候固定 r 指针，挪动 l 指针放大窗口
7. 工夫复杂度 O(n), 空间复杂度 O(n)

var balancedString = function (s) {
  const n = s.length;
  const max = n / 4; // 这里 n 就是 4 的倍数，入参会做好设定的
  const map = new Map();
  map.set("Q", 0);
  map.set("W", 0);
  map.set("E", 0);
  map.set("R", 0);
  for (let ss of s) {map.set(ss, map.get(ss) + 1 );
  }
  let valid = 0; // 有多少个变量满足小于等于 n/4
  [...map.values()].forEach((v) => {if (v <= max) valid++;
  });
  if (valid === 4) return 0; // 非凡状况，间接完结
  let l = (r = 0);
  let ret = Infinity;
  while (r < n) {const rr = s[r];
    map.set(rr, map.get(rr) - 1);
    if (map.get(rr) === max) {
      // 如果减去之后刚好符合要求，则 valid 减少
      valid++;
    }
    while (valid === 4) {
      // 窗口符合要求，开始膨胀窗口
      ret = Math.min(ret, r - l + 1); // 先缓存一个
      const ll = s[l];
      l++;
      map.set(ll, map.get(ll) + 1); // 膨胀滑窗，则滑进来的退出到 map 中去
      if (map.get(ll) > max) valid--;
    }
    // 始终使得 valid 的值少于 4 为止
    r++;
  }
  return ret;
}

1248. 统计「柔美子数组」

@剖析

1. 用 odd 示意窗口里存在的奇数, 只有超过了，就必须膨胀窗口 — 不定滑窗
2. 这里和 930. 和雷同的二元子数组, 992. K 个不同整数的子数组 相似，须要构建双滑窗
3. 工夫复杂度为 O(n)

var numberOfSubarrays = function(nums, k) {
    let ret = 0
    let odd1 = 0
    let odd2 = 0
    let l1 = l2 = r = 0
    while(r<nums.length){const rr = nums[r]
        if(rr%2){
            odd1++
            odd2++
        }
        while(odd1>k){
            // 膨胀 l1
            const ll =nums[l1]
            l1++
            if(ll%2) odd1--
        }
        while(odd2 >= k){
            // 膨胀 l1
            const ll =nums[l2]
            l2++
            if(ll%2) odd2--
        }
        // 这个时候 [l1,l2) 都属于能够合格的数组
        ret+=l2-l1
        r++
    }
    return ret
};

1658. 将 x 减到 0 的最小操作数

剖析

1. 其实这道题截止条件能够转成，设置一个窗口，使得 total – sum === x , 其中 total 就是数组的总和，sum 就是窗口里的值的和；这样移除的值就刚好等于 x 了
2. 在这么多状况下，咱们保护一个窗口的长度最大的时候，那么移除的元素就越少，也就是对应的操作数起码

var minOperations = function(nums, x) {
    const len = nums.length
    const total = nums.reduce((prev,cur) => prev+cur,0)
    if(total<x) return -1 // 边界，如果总和都不达 x, 那就间接跑路吧
    let ret = Infinity // 起码的操作数
    let sum = 0
    let l =r =0
    while(r<len){sum+=nums[r]
        while(total-sum<x){
            // 里面的值曾经小于 x 了，所以须要膨胀窗口
            sum-=nums[l]
            l++
        }
        if(total-sum === x){
            // 符合要求
            ret= Math.min(ret,len-(r-l+1))
        }
        r++
    }
    return ret=== Infinity?-1:ret
};