滑动窗口模板

算法题应用场景:

关键词:

满足XXX条件(计算结果,出现次数,同时包含)

最长/最短

子串/子数组/子序列

例如:长度最小的子数组

滑动窗口使用思路(寻找最长)

核心:左右双指针(L,R)在起始点,R向右逐位滑动循环

​ 每次滑动过程中

如果:窗内元素满足条件,R向右扩大窗口,并更新最优结果

如果:窗内元素不满足条件,L向右缩小窗口

——R到达结尾
//最长模板
初始化left,right,result,bestResult
While(右指针没有到达结尾)
{
    窗口扩大,加入right对应元素,更新当前result
    while(reslut不满足要求)
    {
        窗口缩小,移除left对应元素,left右移
    }
    更新最优结果bestResult
    right++;    
}
返回bestResult;
//最短模板
初始化left,right,result,bestResult
While(右指针没有到达结尾)
{
    窗口扩大,加入right对应元素,更新当前result
    while(reslut满足要求)
    {
        更新最优结果bestResult
        窗口缩小,移除left对应元素,left右移
    }
    right++;    
}
返回bestResult;
上一篇:Minimal安装CentOS 7使用yum报This system is not registered to Red Hat Subscription Management.


下一篇:跨境通申报助手V1.0