滑动窗口算法模板

1.使用场景

找到符合要求数组（字符串）的字数组（子串）

2.核心思想

滑动窗口可以归为快慢双指针，一快一慢两个指针前后相随，中间的部分就是窗口。这个算法的核心问题是什么时候增大窗口,什么时候缩小窗口,如何处理窗口中的数据以及在窗口滑动的哪个阶段更新结果

int left = 0, right = 0;

while (right < nums.size()) {
  // 增大窗口
  window.addLast(nums[right]);
right++;

  while (window needs shrink) {
  // 缩小窗口
  window.removeFirst(nums[left]);
left++;
  }
}

小细节:注意tight初始化为0,每次窗口右移后right++,此时right-left等于窗口中元素的数量

3.算法复杂度

时间复杂度O(N):每一个元素最多只会访问两次(进入一次窗口,移出一次窗口)

4.习题

无重复字符的最长子串(中等)

找到字符串中所有字母异位词(中等)

长度最小的字数组(中等)

最小覆盖子串(困难)

串连所有单词的子串(困难)