【Leetcode每日一刷】滑动窗口：209.长度最小的子数组

本文主要是介绍【Leetcode每日一刷】滑动窗口：209.长度最小的子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、209.长度最小的子数组

1.1：题目

题目链接

1.2：解题思路

• 题型：滑动窗口；时间复杂度：O(n)
  🪧 滑动窗口本质也是双指针的一种技巧，特别适用于字串问题

• ❗❗核心思想/ 关键：左右指针滑窗口，一前一后齐头进。
  详细思路建议看前一篇：【Leetcode每日一刷】数组|双指针篇：977. 有序数组的平方、76. 最小覆盖子串（附滑动窗口法详解）

• 算法框架：注意下面框架中的6个关键点！

  /* 滑动窗口算法框架 */
  void slidingWindow(string s) {// ⭐1)用合适的数据结构记录窗口中的数据情况（以便和所需的可行解进行比对）unordered_map<char, int> window;// ⭐2)// 记录最小符合条件子串的起始索引及长度int start = 0, len = INT_MAX; //根据实际算法所需答案进行调整int left = 0, right = 0;while (right < s.size()) {// c 是将移入窗口的字符char c = s[right];window.add(c)// 增大窗口right++;// ⭐3）进行增大窗口后，更新关于记录当前窗口内数据情况的变量（以便稍后和所需的可行解进行比对）.../*** debug 输出的位置 ***/// 注意在最终的解法代码中不要 print// 因为 IO 操作很耗时，可能导致超时printf("window: [%d, %d)\n", left, right);/********************/// ⭐4）找到可行解——判断左侧窗口是否要收缩（进行更新）while (left < right && window needs shrink) {//进入到这个while里面说明找到一个可行解//⭐5）进行最终的所需的答案更新// eg:在这里更新符合条件的*最小*子串（即最终结果）if (right - left < len) {start = left;len = right - left;}// d 是将移出窗口的字符char d = s[left];window.remove(d)// 缩小窗口left++;// ⭐6）进行缩小窗口后，更新关于记录当前窗口内数据情况的变量（以便稍后和所需的可行解进行比对）...}}
  }

  🌟1. 3)和6)的操作分别是扩大和缩小窗口后的更新操作，等会你会发现它们操作是完全对称的。作用都是更新当前窗口中的数据情况，再拿去和题目所需的可行解进行比对，判断当前窗口内的情况是否可行！

  🌟2. 5)步也很关键，它的作用是：找到一个可行解&更新得到一个可行解后，对题目最终需要的最优答案进行更新！

• 本题思路（依据算法框架）：

  1. ⭐首先设置一个记录当前窗口情况的变量windowSum（作用是方便与所需可行条件进行比较）——记录当前窗口中元素综合
  2. ⭐设置存储最终答案（窗口长度）的变量（作用是得到可行情况后，进行实时更新，以得到最终的最优答案）
  3. ⭐设置left和right指针对窗口大小进行控制
  4. ⭐在窗口的增大和缩小过程中实时更新记录当前窗口情况的变量windowSum
  5. ⭐在得到可行解的情况下，实时更新最终答案

1.3：实现代码——c++

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {//设置一个记录当前窗口情况的变量（即当前窗口内元素总和int windowSum = 0;//算法的最终答案：minLenint minLen = INT_MAX;int left =0, right = 0;while(left <= right && right < nums.size()){//先记下窗口待新增元素int a = nums[right];right++;//增大窗口后，更新当前窗口中的情况windowSum += a;while(left <= right && windowSum >= target){//首先，因为进入循环就代表得到哦一个可行结果，立马更新答案minLen = min(minLen, right - left);//先记下窗口待减少元素int b = nums[left];left++;//窗口减小后，更新记录当前窗口的元素windowSum -= b;}}return minLen == INT_MAX ? 0 : minLen;}
};

这篇关于【Leetcode每日一刷】滑动窗口：209.长度最小的子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---