[76. Minimum Window Substring]

(https://leetcode.cn/problems/minimum-window-substring/)

滑动窗口

• 此题需要求s中包含t的最小字符串，运用滑动窗口可解

• 定义：我们需要定义两个哈希表mapS和mapT，限制窗口左右的left和right，求得字符串的最小长度resultLength以及此字符串的开始位置start

• 思路：

  • 通过移动right指针不断扩张窗口。当窗口包含t全部所需的字符后，若能收缩，则收缩窗口直到最小
  • mapT存储所有t字符，mapS每次循环判断当前这个字符在mapT中是否存在，存在则加入
  • check()判断窗口内是否含有t中全部字符，若含有则说明此窗口符合题目条件，再计算当前窗口长度是否小于resultLength，小于则更新resultLength和开始位置start
  • 收缩时，需要看left所指字符是否在t中，若存在--mapS[ s[ left ] ]

• 实现：

  class Solution {
  public:
      string minWindow(string s, string t) {
          //s小于t则不可能符合题意
          if( s.size() < t.size() ) return "";
  
          //mapT存储所有t字符
          for( const auto& c : t )
          {
              ++mapT[c];
          }
  
          //扩张收缩窗口
          for( ; right < s.size(); ++right)
          {
  
              //判断当前这个字符在mapT中是否存在，存在则加入mapS
              if( mapT.find( s[right] ) != mapT.end() )
              {
                  ++mapS[s[right]];
              }
  
              //若当前窗口包含t所有字符
              while( check() && left <= right )
              {
                  
                  //判断是否更新开始位置和最小长度
                  if( right - left + 1 < resultLength )
                  {
                      resultLength = right - left + 1;
                      start = left;
                  }
  
                  //left所指字符是否在t中
                  if( mapT.find(s[left]) != mapT.end() )
                  {
                      --mapS[s[left]];
                  }
  
                  ++left;
              }
  
          }
  
          //若没有符合题意的字符串
          if(resultLength == INT32_MAX) return "";
  
          s = s.substr( start, resultLength );
          return s;
      }
  
      //判断当前窗口包含t所有字符
      bool check()
      {
          for( const auto& f : mapT )
          {
              if( mapS[ f.first ] < f.second )
              {
                  return false;
              }
          }
          return true;
      }
  
  private:
      unordered_map<char, int> mapS, mapT;
      int left = 0, right = 0;
      int resultLength = INT32_MAX, start = 0;
  };
  

  • 时间复杂度：O（n）

    空间复杂度：O（n）