[Algorithm][滑动窗口][长度最小的子数组] + 滑动窗口原理

0.滑动窗口原理讲解

• 滑动窗口：“同向双指针”
• 滑动窗口可处理「⼀段连续的区间」问题
• 如何使用？
  1. left = 0, right = 0
  2. 进窗口
  3. 判断
     • 是否出窗口
  4. 更新结果 -> 视情况而定
     • 可能在出窗口前
     • 可能在进窗口之后
• 具体原理解析将结合**「长度最小的子数组」**来说明

1.长度最小的子数组

1.题目链接

• 长度最小的子数组

2.算法原理讲解

• 此问题分析的对象是**「⼀段连续的区间」，因此可以考虑「滑动窗⼝」**的思想来解决

• 让滑动窗⼝满⾜：

  • 从i位置开始，窗⼝内所有元素的和⼩于target
  • 当窗⼝内元素之和第⼀次⼤于等于⽬标值的时候，就是i位置开始满⾜条件的最⼩⻓度

• 做法：

  • 如果窗⼝sum >= target：
    • 更新结果，并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果
      • 因为左端元素可能很⼩，划出去之后依旧满⾜条件
  • 如果窗⼝sum不满⾜条件：
    • right++，让下⼀个元素进⼊窗⼝
      

• 为何滑动窗⼝可以解决问题，并且时间复杂度更低？

  • 这个窗⼝寻找的是：以当前窗⼝最左侧元素(记为left1)为基准，符合条件的情况
    • 即：从left1开始，满⾜sum >= target时的最右侧(记为right1)能到哪⾥
  • 既然已经找到从left1开始的最优的区间，那么就可以⼤胆舍去left1
    • 但是如果继续像暴力求解⽅法⼀样，重新开始统计第⼆个元素(left2)往后的和，势必会有⼤量重复的计算
      • 因为在求第⼀段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候⽤上的
  • 此时，rigth1的作⽤就体现出来了，只需将left1这个值从sum中剔除
    • 从right1这个元素开始，往后找满⾜left2元素的区间
      • 此时right1也有可能是满⾜的，因为left1可能很⼩，sum剔除掉left1之后，依旧满⾜⼤于等于 target
  • 这样就能省掉⼤量重复的计算
  • 总结：利用单调性，规避了很多没有必要的枚举行为
    • 此处的单调指滑动窗口内sum的单调性，而不是数组原始数据的单调性

• 时间复杂度：$O(N)$

  • 虽然代码是两层循环，但是left指针和right指针都是不回退的，两者最多都往后移动n次

3.代码实现

int MinSubArrayLen(int target, vector<int>& nums) 
{int sum = 0, len = INT_MAX;for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right]; // 进窗口while(sum >= target) // 判断{len = min(len, right - left + 1); // 更新结果sum -= nums[left++]; // 出窗口}}return len == INT_MAX ? 0 : len;
}