双指针之滑动窗口(长度最小的子数组 和 和为s的连续正数序列)

双指针之滑动窗口 (长度最小的子数组;和为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 需要的结果变量; } }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwpsgj.html