算法思想总结：滑动窗口算法

                                                      创作不易，感谢三连 

一.长度最小的数组

. - 力扣（LeetCode）长度最小的数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
           int len=INT_MAX,n=nums.size(),sum=0;//len必须要给一个很大的数，否则
           for(int left=0,right=0;right<n;++right)
           {
            sum+=nums[right];//right进窗口
            while(sum>=target)//符合条件后进行更新，然后出窗口
            {
                len=min(len,right-left+1);//更新长度
                sum-=nums[left++];
            }
           }
           return len==INT_MAX?0:len;
    }
};

 二.无重复字符的最长字串

. - 力扣（LeetCode）无字符的最长字串

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        int hash[128]={};//计数
        int len=0, n=s.size();
        for(int left=0,right=0;right<n;++right)
        {
            ++hash[s[right]];//进窗口
            while(hash[s[right]]>1)  --hash[s[left++]];//出窗口
            len=max(len,right-left+1);//更新长度
        }
        return len;
    }
};

三.最大连续1的个数

. - 力扣（LeetCode）最大连续1的个数

class Solution {
public:
    int longestOnes(vector<int>& nums, int k)
    {
         int len=0;
         for(int left=0,right=0,zero=0;right<nums.size();++right)
            {
                if(nums[right]==0) ++zero;//进窗口
                while(zero>k) if(nums[left++]==0) --zero;//出窗口
                len=max(len,right-left+1); 
            }
            return len;
    }
};

 四.将x减到0的最小操作数

. - 力扣（LeetCode）将x减到0的最小操作数

class Solution {
public:
    int minOperations(vector<int>& nums, int x) 
    {//将问题转化为求一个最长子数组 其大小正好==sum-x
        int ret=-1;
        int sum=accumulate(nums.begin(),nums.end(),0);//计算数组的总和
        int target=sum-x;//记录目标值
        if(target<0) return -1;//细节处理
        for(int left=0,right=0,temp=0,n=nums.size();right<n;++right)
        {
            temp+=nums[right];//进窗口
            while(temp>target)  temp-=nums[left++];//出窗口
            if(temp==target)   ret=max(ret,right-left+1);//更新结果
        }
        return ret==-1?-1:nums.size()-ret;
    }
};

 五.水果成篮

. - 力扣（LeetCode）水果成篮

class Solution {
public:
    int totalFruit(vector<int>& fruits) 
    {
       int hash[100001]={0};
       int ret=0,n=fruits.size();
       for(int left=0,right=0,kinds=0;right<n;++right)
       {
           if(hash[fruits[right]]++==0) ++kinds;//进窗口
           while(kinds>2)  if(--hash[fruits[left++]]==0) --kinds;
           ret=max(ret,right-left+1);
       }
       return ret;
    }
};

六.找到字符串种所有字母异位词

. - 力扣（LeetCode）找到字符串种所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ret;
        int hash1[26]={0};//用来统计p的元素个数
        for(char ch:p) ++hash1[ch-'a'];
        int hash2[26]={0};//用来统计滑动窗口的元素个数
        int m=p.size();
        for(int left=0,right=0,count=0;right<s.size();++right)//count用来记录有效字符的个数
           {
            char in=s[right];
           if(++hash2[in-'a']<=hash1[in-'a'])  ++count;//进窗口的同时统计有效字符个数
            if(right-left+1>m)//判断  出窗口
            {
                char out=s[left++];
               if(hash2[out-'a']--<=hash1[out-'a'])  --count;
            }
            if(count==m) ret.push_back(left);
           }
           return ret;
    }
};

七.最小覆盖字串

. - 力扣（LeetCode）最小覆盖字串

class Solution {
public:
    string minWindow(string s, string t) 
    {
        int hash1[128]={0};//统计t字符串个元素的出现次数
        int kinds=0;//用来统计种类
        for(char ch:t) if(hash1[ch]++==0)  ++kinds;
        int hash2[128]={0};//统计s字符串中滑动窗口的元素出现次数
        int begin=-1,minlen=INT_MAX;//用来记录返回值情况
        for(int left=0,right=0,count=0;right<s.size();++right)
        {
            if(++hash2[s[right]]==hash1[s[right]])  ++count;//进窗口的同时统计窗口内元素种类
            while(count==kinds)//当种类都一样时，可以去更新结果
            {
                if(right-left+1<minlen)//因为还需要更新begin，所以不能直接用min
                {
                    minlen=right-left+1;
                    begin=left;
                }
                if(hash2[s[left]]--==hash1[s[left]]) --count;
                ++left;
            }
        }
         return begin==-1?"":s.substr(begin,minlen);
    }
};

 八.串联所有单词的子串

. - 力扣（LeetCode）串联所有单词的子串

 

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        int m=words.size();//单词个数
        int len=words[0].size();//每个单词的长度
        vector<int> ret;//用来返回
        unordered_map<string,int> hash1;//用来记录word的各个单词出现次数
        for(auto s:words) ++hash1[s];
        for(int i=0;i<len;++i)//要使用len次滑动窗口
        {
             unordered_map<string,int> hash2;//用来记录滑动窗口的各个单词出现次数
           for(int left=i,right=i,count=0;right+len-1<s.size();right+=len)//count用来有效子串
           {
                string in=s.substr(right,len);
                if(++hash2[in]<=hash1[in])  ++count;//进窗口顺便维护count
                if(right-left+1>len*m)//如果超过窗口的大小，就要出窗口
                {
                    string out=s.substr(left,len);
                    if(hash2[out]--<=hash1[out]) --count; //出窗口前要先维护count
                    left+=len;//出窗口要更新left
                }
                if(count==m) ret.push_back(left);//如果count==m，说明有效子串达到要求
           }
        }
        return ret;
    }     
};

九.滑动窗口总结

   当题目涉及到子串或者是子数组，都可以考虑到使用滑动窗口来进行解决

    但是有一个需要注意的地方就是如果涉及到窗口求和的话。要保证数都是正整数，否则就不满足单调性。如下图这一题

涉及到不同的种类需要统计数量的时候，常常会用到哈希表！！ （5-7题）

后面有类似题目会持续更新！！