一. 基础

• 可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。

二. 如何判断使用滑动窗口算法

• 往往类似于“请找到满足xx的最x的区间（子串、子数组）的xx”这类问题都可以使用该方法进行解决。
• 最小值 Minimum value
• 最大值 Maximum value
• 最长值 Longest value
• 最短值 Shortest value
• K值 K-sized value

三.套路

1. 模板

/* 滑动窗口算法框架 */

var slidingWindow = function(s) {
    const win =new Map()
    let left=0,right=0
    ...
    while(right<s.length){
        const c=s[right]        // c 是将移入窗口的字符
        right++                 // 右移窗口
           ...                       // 进行窗口内数据的一系列更新
           
        while(win.get(c)>1){     // 判断左侧窗口是否要收缩
            const d=s[left]        // d 是将移出窗口的字符
            left++                  // 左移窗口
          ...                           // 进行窗口内数据的一系列更新
        }
        ...
    }
   ...
};

2.滑动窗口算法的思路：

1. 在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0 ，把索引左闭右开区间 [left, right) 称为一个「窗口」。

2. 不断地增加 right 指针扩大窗口 [left, right) ，直到窗口中的字符串符合要求（包含了 T 中的所有字符）.

3. 此时停止增加 right ，转而不断增加 left 指针缩小窗口 [left, right) ，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left ，都要更新一轮结果。

4. 重复第2和第3步，直到 right 到达字符串 S 的尽头。needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。

3.开始套模板之前，要思考以下四个问题：

1. 当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

2. 什么条件下，窗口应该暂停扩大，开始移动_left_ 缩小窗口？

3. 当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

4. 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

四.例题

LeetCode 3

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  const win = new Map();
  let left = 0,
    right = 0;
  let res = 0;
  while (right < s.length) {
    const c = s[right];
    right++;
    win.set(c, (win.get(c) || 0) + 1);
    while (win.get(c) > 1) {
      const d = s[left];
      left++;
      win.set(d, win.get(d) - 1);
    }
    res = Math.max(res, right - left);
  }
  return res;
};

LeetCode 219

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    const set =new Set()
    for(let i=0;i<nums.length;i++){
        if(set.has(nums[i])){
            return true
        }
        set.add(nums[i])
        if(set.size>k){
            set.delete(nums[i-k])
        }
    }
    return false
};