两根指针的前向型应用

两根指针的前向型应用又叫滑动窗口,用于解决数组或者字符串问题

和暴力解法相比时间复杂度更低,暴力的枚举算法大多使用两层 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 的影响)
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,354评论 0 33
  • 指针是C语言中广泛使用的一种数据类型。 运用指针编程是C语言最主要的风格之一。利用指针变量可以表示各种数据结构; ...
    朱森阅读 8,814评论 3 44
  • thiele插值算法 1点插值算法 function [C,c]=thiele(X,Y,Z)%X为插值点横坐标,Y...
    00crazy00阅读 6,258评论 0 4
  • 熵与原罪 作者认为阻碍心智成熟最大的障碍是懒惰,而懒惰就是人类的原罪。作者说,伊甸园中的亚当和夏娃,正是因为懒惰没...
    书青麦阅读 2,454评论 0 0
  • 阿G正传——11 下午三点半的 阳光,凝视着我 隔着布满故事的灰尘看我 故事里云淡风轻 陌生的动物,...
    阿G先生和猫阅读 2,372评论 4 10