双指针之滑动窗口 (长度最小的子数组;和为s的连续正数序列)
1, 什么时候使用?
(与子数组/字符串 有关的题目)~如果给了某个具体值的target,即用滑动窗口
不然就双指针(一般做法,左边< 右边,依据条件左边和右边都不断靠近)
滑动窗口:是双指针的题目
找出一个数组中满足一定条件的子数组问题,字符串也可以看成数组。看到子数组问题,就是DP回溯滑动窗口这三种之一
2,滑动窗口的通用框架 1:(例题:209_长度最小的子数组)
(做题特点一:题目给定了具体的值target,这个target条件的可能弹性空间比较大了
【例如题目 要求某种情况下>= target】,而大于target的可能情况就会比较多了
* ① 先移动右指针确定窗口的大致可能范围(在这大致可能范围里找到最优范围),然后暂时固定住右指针,
* ② 在满足条件(满足target下):不断的移动左指针,缩小窗口
* ③ 当不满足target了,又开始移动右指针,然后。。。。。又确定下来窗口的大致可能范围
(在这大致可能范围里找到最优范围),然后暂时固定住右指针。。。
* 特点2,形式上的特点(左右指针移动的方向):是一开始左右指针,同方法移动)
public class 滑动窗口的通用框架 1{ public String slidingWindow(String s, String t) { // 起始的时候,都位于 0,同方向移动 int left = 0; int right = 0; int sLen = s.length(); while (right < sLen) { char c = s.charAt(right); right++; //对状态做修改 while ( 满足某种条件 ) { //更新ans可能的地方之一 char c1 = s.charAt(left); left++; //对状态做修改 } //更新ans可能的地方之二 } return 需要的结果变量; } }