[算法]滑动窗口

案例：对输入字符串求取其最长无重复字符子串
1

暴力方式：在所有子串中找出满足条件最长的，复杂度O(n²)
采用滑动窗口可简化过程

滑动窗口 —— 双指针框选一段存储区域

解决查找满足一定条件连续区间的问题

基本思路

1. 需要头尾指针来框定区间 [每次移动前获取区间内容以备后用]
2. 头尾指针从起始端开始，先移动尾指针直至（不）满足条件
   ，移动头指针直至再次（不）满足条件，再次移动尾指针
3. 期间在满足目标时，缓存结果

重难点

1. 必须针对连续区间问题，如子串，子数组等
2. 如何移动，条件的确定是需要思考的，如根据实际问题指针多移可显著减少运算
   ”求最短“往往头尾指针都考虑满足的情况以达到缩小区间的目的，
   "求最长"头指针需要移动到满足条件的位置
3. 缓存目标结果的时机需要确定，这一步还可提前筛选出最终结果

应用

1. 对输入字符串求取其最长无重复字符子串，输出‘字符串’: 长度

function LongestSubstring(str) {
   let left = 0 // 头指针
   let right = 0 // 尾指针
   let count = str.length ? 1 : 0 // 用于缓存目标结果
   let subStr = str[0] || '' // 用于缓存目标结果
   while (right < str.length) {
      let subTemp = str.slice(left, right) // 获取区间内容
      let charIndex = subTemp.indexOf(str[right])
      if (~charIndex) { // 比较下一位元素是否重复
         // 重复（不满足条件）头指针应移过重复位置
         left = left + charIndex + 1
         right++
      } else {
         right++ // 不重复（满足条件）继续移动尾指针
         // 缓存目标结果
         subTemp = str.slice(left, right)
         if (subStr.length < subTemp.length) {
            subStr = subTemp
            count = subTemp.length
         }
      }
   }
   return `'${subStr}':${count}`
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24