算法题应用场景:
关键词:
满足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;