【LeetCode 04】滑动窗口法总结

简介: 【LeetCode 04】滑动窗口法总结

滑动窗口是双指针法的一种高级用法。 双指针法。滑动窗口就是不断调节子数组的起始位置和终止位置,得到我们想要的结果。解题的关键在于如何移动起始位置。

如下图所示,设定滑动窗口(window)大小为 3,当滑动窗口每次划过数组时,计算当前滑动窗口中元素的和,得到结果 res

一、适用条件

适用条件为:

  • 数组
  • 字符串
  • 求解的结果具有某种特质的子数组或者子字符串。

二、方法总结

实现滑动窗口需要确定以下三点:

  • 窗口内的元素
    保持窗口内数值总和大于或等于numsSize的长度最小的连续子数组。
for(int j=0;j<numsSize;j++){
    sum+=nums[j];
    while(sum>=numsize){
    xxx;
    sum-=nums[i++];//滑动窗口的精髓,不断调节子数组的初始位置
}
}
  • 如何移动窗口的起始位置
    当前窗口值的值大于numsize,则窗口向前移动,也就是i指针向前移动,缩小
while(sum>=numsize){
    subLength=j-i+1;//获取子数组长度
    result=result<subLength?result:subLength;
    sum-=nums[i++];//滑动窗口的精髓,不断调节子数组的初始位置
}
  • 如何移动窗口的终点位置
    通过for循环遍历指针即可
for(int j=0;j<numsSize;j++){
    
}

三、窗口滑动具体案例

根据例题:

  • step1:滑动窗口的起始位置
  • step2:移动窗口的结束位置,记录窗口值
  • step3:移动窗口的起始位置当前窗口值的值大于numsize,则窗口向前移动,也就是i指针向前移动,缩小
int minSubArrayLen(int target, int* nums, int numsSize){
   int result=INT32_MAX;//更新值
   int i=0;//step1:滑动窗口的起始位置
   int sum=0;//滑动窗口的数值之和
   int subLength;//子数组的长度
    
    for(int j=0;j<numsSize;j++){//step2:移动窗口的结束位置,记录窗口值
        sum+=nums[j];
        
        //step3:移动窗口的起始位置当前窗口值的值大于numsize,则窗口向前移动,也就是i指针向前移动,缩小
        while(sum>numsSize){
            subLength=j-i+1;
            result=result<subLength?result:subLength;
            sum-=nums[i++];//滑动窗口的精髓,不断调节子数组的初始位置
        }
    }
    return result==INT32_MAX?0:result;//查看有没有被赋值
}


目录
相关文章
|
5月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
3天前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
11 1
|
2月前
|
存储 Python
【Leetcode刷题Python】239. 滑动窗口最大值
文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。
23 0
|
4月前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
25 1
|
3月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
4月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
4月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
4月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
40 0
|
4月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
4月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串