Sliding Window

滑动窗口

概念

  滑动窗口简单来讲就是一个子序列在主序列上滑动的一个过程，这个子序列满足某种条件。

  它是动态规划问题的一个子集，主要用在解决数组或链表上的问题，常常涉及到求最长/最短子序列。

  一个窗口有左右两个指针（left，right），两个指针以一前一后的速度前进，当满足某种条件的时候停止算法。

如何判断一个问题是滑动窗口问题？

  我们可以通过一些简单的特征来判断一个问题是否可以使用滑动窗口来解答：

• 该问题的数据结构是数组/字符串类型，且是可迭代的。

• 该问题要求解出该数组/字符串的某个最长/最短子序列，或某个目标值。

• 该问题能够用简单的暴力解法来解答，时间复杂度往往O（n2）以上。

  最显著的特征是，题目要求的往往是某种最优的答案，比如满足给定条件的最长的序列或最短的序列。

  滑动窗口的优势在于，它的时间复杂度往往是O（n），空间复杂度O（1）。

参考模板

  这是一个简单的模板，它很好的归纳出了滑动窗口核心思想：

leetcode题目

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

分析：这是比较典型的求解字符串规定条件的子串问题。

首先，题目要求不含重复字符的最长子串，也就是说我们需要有一个条件用来判断当前字符是否在子串中出现过。我们这里可以通过哈希表来实现该判断条件。

其次，我们观察发现，当一个位置(right)出现重复字符的时候，我们只需要从那个被重复的字符的位置重新开始计算即可，也就是把左指针 left 设置为那个字符的索引，之前的全部字符都可以抛弃掉。

核心部分：

• 哈希表       ---->      判断当前字符是否在前面出现过，存储字符的索引

• 最长子串长度 = 当前字符索引（right） - 子串起始索引（left） 

• 确定边界问题   ---->   连续相同字符、当前字符为初始字符等

代码实现：

边界问题：

  解题的时候，一个非常重要的事情就是确定边界问题。

  在这题当中，判断条件为：若当前字符（right）没有出现过，则计算该子串的长度，否则将左指针（left）的位置重置为当前字符（right）的位置。

  这里有一个问题，假如输入为 “txxmast”，当右指针right移动到最后一位 t 时，此时的子串为"xmas"，按理说 t 并没有出现在这个子串当中，此时的字符串长度应为5。但是由于之前的"t"在哈希表中的索引还是0，因此最后一个"t"会因为已经出现在哈希表里，而被当成重复字符不进入计算，导致bug。

  因此，针对此边界问题，我们需要再加入一个判断：若当前字符已经存在哈希表中，但它是上一个字符串里的字符（即它在哈希表中的索引小于当前right），则当前字符不属于当前子串，仍计算长度。

  也就是上图中红色圈圈的部分。

  参考：

https://zhuanlan.zhihu.com/p/104983442

https://blog.csdn.net/qq_19446965/article/details/104579511

https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66