在数组中,有一类关于连续字串最优解的问题,这个时候可以使用滑动窗口解法。
它的核心思想与对撞指针相似,维护两个指针,右指针遍历数组长度,当右指针前进到某一点不满足最优条件的时候,缩小窗口,左指针前进,重复这个操作直到右指针到达数组长度。
例子
以leetcode76号题目为例,该题需要寻找S的最小字串,其包含T的每一个字母。
按照滑动窗口的思想,两个指针间的字串必须满足题目中包含T每一个字母的要求,
所以初始的时候先移动右指针得到初始窗口:
|
|
这个地方需要注意指针的含义,r,l是闭区间意味着在[l,r]中的字串都已经写入表中,之后再做是否满足条件的判断。当然这个地方也可以改成开区间,也就是说r是一个尾后指针,这样的话这部分代码就要改为这样:
|
|
初始化窗口之后,就可以开始移动另外一个指针,如果移动之后还满足条件,就重新取最优的字串,重复这个步骤直到右指针到达数组长度
|
|
这题还有一个巧妙的方法,就是可以把上面两个循环和为一个,增加一个变量count(匹配字串的个数),如果count大于待匹配字串的长度的时候,可以认为已经把窗口拉到了满足条件的长度,代码如下:
|
|
完整代码可参考:http://blog.csdn.net/feliciafay/article/details/44535301