两根指针的前向型应用又叫滑动窗口,用于解决数组或者字符串问题
和暴力解法相比时间复杂度更低,暴力的枚举算法大多使用两层 for 循环的方式,可以理解为定义 i 和 j 两根指针,每更新一次 i,j 都要从 i 开始重新枚举(不是从 i+1 开始,从 i+1 开始意味着漏掉长度为1的情形);
滑动窗口的做法优化了暴力解法,通过定义 i 和 j 两根指针,两根指针交替向前移动,每更新一次 i, j 只判断下一位置 j+1 是否满足条件,并不回到 i+1的位置重新做重复运算,保证了算法的时间复杂度为 O(n) 级别
这里重复运算要特意说明下:两根指针向前移动时,起于位置 i,终止于位置 j,j+1 位置元素及其后的所有元素对于当前起始点 i 而言必然都不符合要求,所以我们开始向前移动位置 i 但对于下一次的起于 i+1,j 从当前位置不断向前遍历的操作而言,i+1 到 j 这段区间的元素已经在上一次操作中判断过了,无需再重复判断,所以我们只需判断 j+1,j+2 ... 直到某一位置 j 不符合要求,再进行更新 i 继续从当前位置往后寻找新的 j 的操作
窗口型指针类题目移动模板
通过对两层 for 循环进行改进
伪代码如下:
for (i = 0; i < n; i++) {
while (j < n) {
if (满足条件)
更新 j 状态)
j++
else(不满足条件)
break
}
更新 i 状态(i 向前移动去除 i 的影响)
}