leetcode 209 3 滑动窗口

 class Solution {
 public:
     int minSubArrayLen(int s, vector<int>& nums)
     {
         ,r=-;　　　　　　　　　　//由于数组是[]区间，所以这样使之不包含任何元素
         ;　　　　//记录长度
         ;　　　　　　　　　　//记录子数组的和
         while(l< nums.size())　　　　//滑动过程，每一次while都走一步
         {

             <nums.size()&&sum<s)//同时保证有边界到底后不再继续拓展
                 sum+=nums[++r];
             else
                 sum-=nums[l++];

             if(sum>=s)　　　　　　　　　　//每步生成子数组都判断条件
                 res=min(res,r-l+);
         }
         ) ;//没有更新，就是无解，就返回0
         else return res;
     }
 };

这是一道与连续子数组相关的问题，如果尝试用暴力求解，每次遍历得到子数组，则是O(n^3)。

为什么考虑用滑动窗口？

因为滑动窗口能不遗漏的获取连续子数组（这里的连续很关键），并且，如果窗口步长为1，则可以对每一种情况都进行条件判断，随时更新。

具体实现思路：

对于某一子数组[i,j],考虑其内部元素是否达到要求，未达到要求，则扩大数组，考虑到数组应是从头开始的，所以扩张时是对j扩张，每一次扩张都获得一个新子数组，之后进行子数组条件判断，只要没达到要求，就再扩张j，直到达到要求。
倘若达到要求了，那么记录下这一长度。可是单纯达到要求还不够呀，因为我们要的是对所有的连续子数组进行遍历查看。
于是保持j不变，使i++，这样获得了一个新的子数组，重复子数组条件判断，仍然满足要求，则更新长度，若没有满足要求了，就又回到1.

总结：

　　简单来说，滑动窗口就是一种以单步走保证每种情况不遗漏的解法，最后时间复杂度只是O（n）（正比于走的路子2n）。

再来看leetcode 3。

 class Solution {
 public:
     int lengthOfLongestSubstring(string s)
     {
         ]={};
         ,r=-;
         ;
         while(l<s.size())
         {
             <s.size() && freq[s[r+]]==)
             {
                 r++;
                 freq[s[r]]++;
             }
             else
             {
                 freq[s[l++]]--;
             }

             res=max(res,r-l+);
         }
         return res;
     }
 };

可以看出，滑动窗口的模板是相对比较固定的。

对于一个滑动窗口，最大的循环是while(l<s.size())，是为了使得左边界也到达最大。之后是if(r+1<s.size() && freq[s[r+1]]==0)，前半边是为了右边界在达到最大时不再继续扩张。

而这一if else循环是为了变动滑动窗口。

巴特西

leetcode 209 3 滑动窗口

最新文章

热门文章