滑动窗口概念

维护一个窗口[left,right), 当前窗口内的元素没有达到要求的解时，继续扩大right, 直到窗口内的元素达到要求的解。注意此时只是一个解，而不是最优解，要想得到最优解需要left++来缩小窗口。因此求解过程分为两步：

  1. right++ 来增加窗口大小寻找一个解
  2. left++来缩小窗口大小寻找最优解

关键点：什么时候窗口停止增大并开始减小

滑动窗口实战1

图片.png

  1. 当窗口内的字符包含了t中的所有字符时，窗口停止增大
  2. 记录当前窗口内的解的长度，长度更短则更新
  3. 开始缩小窗口，判断缩小窗口后的窗口内的字符是否还满足条件，如果满足条件继续计算窗口大小，并更新解
  4. 重复以上过程直到遍历完s
  1. class Solution {
  2. public:
  3.     string minWindow(string s, string t) {
  4.         unordered_map<char,int> window,need;
  5.         //need记录t中各类字符出现的次数
  6.         for(char c:t)
  7.             need[c]++;
  8.         //初始化窗口左右边界
  9.         int left=0,right=0;
  10.         //valid记录的是窗口内满足条件的字符种类数
  11.         int valid=0,len=INT_MAX;
  12.         //start记录最优解的开始位置
  13.         int start=0;
  14.         while(right<s.size())
  15.         {
  16.             char c=s[right];
  17.             right++;//右边界先增大 因此窗口是[left,right) 左闭右开
  18.             if(need.count(c))//当前字符是t中的
  19.             {
  20.                 window[c]++;//窗口内对应种类的字符+1
  21.                 if(window[c]==need[c])//某种字符个数满足
  22.                     valid++;
  23.             }
  25.             while(valid==need.size())//只要窗口内的字符是符合条件的一个解 就继续优化解
  26.             {
  27.                 char d=s[left];//获取窗口左边界字符
  28.                 if(need.count(d))//左边界字符是t中的
  29.                 {
  30.                     if(need[d]==window[d])//如果该类字符已经满足条件 移掉它之后 符合条件的种类数就会-1
  31.                         valid--;
  32.                     window[d]--;//窗口内该类字符-1
  33.                 }
  34.                 if(right-left<len)//窗口更小则更新
  35.                 {
  36.                     len=right-left;
  37.                     start=left;//记录新的解的开始位置
  38.                 }
  39.                 left++;//此时left++ 因为前面需要right-left
  40.             }
  42.         }
  43.         return len==INT_MAX?"":s.substr(start,len);
  45.     }
  46. };
  47. //O(n)  n是s的长度
  48. //O(C)  c是t中的字符种类数

滑动窗口实战2

图片.png
这道题比较于上一道题目，区别有以下几点：

  1. 窗口收缩条件是窗口内的字符个数=s1.size(), 因为是排列，所以不能有多余的字符
  2. 不存在最优解，找到一个解即返回true
  1. class Solution {
  2. public:
  3.     bool checkInclusion(string s1, string s2) {
  4.          unordered_map<char,int> window,need;
  5.         //need记录t中各类字符出现的次数
  6.         for(char c:s1)
  7.             need[c]++;
  8.         //初始化窗口左右边界
  9.         int left=0,right=0;
  10.         int valid=0;
  11.         while(right<s2.size())
  12.         {
  13.             char c=s2[right];
  14.             right++;
  15.             if(need.count(c))
  16.             {
  17.                 window[c]++;
  18.                 if(window[c]==need[c])
  19.                     valid++;
  20.             }
  21.             if(right-left==s1.size())//缩小条件
  22.             {
  23.                if(valid==need.size())//找到一个解即返回true
  24.                     return true;
  25.                 char d=s2[left];
  26.                 if(need.count(d))
  27.                 {
  28.                     if(window[d]==need[d])
  29.                         valid--;
  30.                     window[d]--;
  31.                 }
  32.                 left++;
  34.             }
  35.         }
  36.         return false;
  37.     }
  38. };
  39. //O(s2.size())
  40. //O(c) c是s1中含有的字符种类数

滑动窗口实战3

图片.png
这一题和上一题类似，需要改动的只有一处：

  1.   if(valid==need.size())//找到一个解即返回true
  2.        return true;
  4.   if(valid==need.size())//记录下所有的解
  5.        ans.push_back(left);
  1. class Solution {
  2. public:
  3.     vector<int> findAnagrams(string s, string p) {
  4.          vector<int> ans;
  5.          unordered_map<char,int> window,need;
  6.         //need记录t中各类字符出现的次数
  7.         for(char c:p)
  8.             need[c]++;
  9.         //初始化窗口左右边界
  10.         int left=0,right=0;
  11.         int valid=0;
  12.         while(right<s.size())
  13.         {
  14.             char c=s[right];
  15.             right++;
  16.             if(need.count(c))
  17.             {
  18.                 window[c]++;
  19.                 if(window[c]==need[c])
  20.                     valid++;
  21.             }
  22.             if(right-left==p.size())
  23.             {
  25.                 if(valid==need.size())
  26.                      ans.push_back(left);   
  27.                 char d=s[left];
  28.                 if(need.count(d))
  29.                 {   
  30.                     if(window[d]==need[d])
  31.                         valid--;
  32.                     window[d]--;
  33.                 }
  34.                 left++;
  36.             }
  37.         }
  38.         return ans;
  40.     }
  41. };
  42. //O(s.size())
  43. //O(c) c是p中含有的字符种类数
  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String p) {
  4.         List<Integer> ans=new ArrayList<>();
  5.         HashMap<Character,Integer> window=new HashMap<>();
  6.         HashMap<Character,Integer> need=new HashMap<>();
  7.         for(int i=0;i<p.length();i++)
  8.         {
  9.             char c=p.charAt(i);
  10.             need.put(c,need.getOrDefault(c,0)+1);
  11.         }
  12.         int valid=0;
  13.         int left=0,right=0,n=s.length();
  14.         while(right<n)
  15.         {
  16.             char c=s.charAt(right);
  17.             right++;
  18.             if(need.containsKey(c))
  19.             {
  20.                 window.put(c,window.getOrDefault(c,0)+1);
  21.                 if(window.get(c).equals(need.get(c)))
  22.                     valid++;
  23.             }
  24.             if(right-left>=p.length())
  25.             {
  26.                 char c2=s.charAt(left);
  27.                 if(valid==need.size())
  28.                 {
  29.                     ans.add(left);
  31.                 }
  32.                 if(need.containsKey(c2))
  33.                 {
  34.                     if(window.get(c2).equals(need.get(c2)))
  35.                         valid--;
  36.                     window.put(c2,window.getOrDefault(c2,0)-1);
  37.                 }
  38.                 left++;
  39.             }
  40.         }
  41.         return ans;
  42.     }
  43. }

滑动窗口实战4

图片.png
此题判断窗口收缩的条件时window[c]>1 并且可能需要多次移动 需要注意的时，对于不同的情况，有的窗口移动一次即可（比如实战2 3 此时可以用if语句），有的窗口需要移动多次（比如实战1 4 此时需要使用while语句）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
          unordered_map<char,int> window;
          int left=0,right=0;
          int maxLen=0;
          while(right<s.size())
          {
              char c=s[right];
              right++;
              window[c]++;
              //需要用while 比如abcdd 需要left移动4次
              while(window[c]>1)
              {
                  char d=s[left];
                  window[d]--;
                  left++;
              }
              maxLen=max(right-left,maxLen);
          }
          return maxLen;
    }
};
//O(s.size())
//O(c) c是s中含有的字符种类数