这题还是很有难度的。通过数组记录元素的长度，将目标数组与其进行比较，再对相应的子串进行缩小，并记录相应的起点与长度。

 

提取包含子串的最小窗口，可以是无序的。

 

1、建立一个256个大小的ASCII数组，统计子串中每个字符出现的次数；

 

2、用两个指针，一个指针表示窗口的起始位置，一个不断后移直至这个窗口包含了完整的子串；

 

3、用一个变量指示窗口中是否包含了子串：如果某个字符出现的次数不够或正好足够，变量加1；

 

4、压缩窗口。如果某字符出现的次数比子串的多，则说明后面有更小的窗口包含子串，可以后移；

 

5、记录下该窗口的长度，如果最小，保留起始位置。

 

string minWindow(string S, string T)      {          if (S.empty())return " ";          if (S.size() < T.size())return " ";          const int ASCII_MAX = 256;          //定义数组，表示相应字符出现的次数          int appeared_count[ASCII_MAX];          int expected_count[ASCII_MAX];          fill(appeared_count, appeared_count + ASCII_MAX, 0);          fill(expected_count, expected_count + ASCII_MAX, 0);          //统计目标串每个元素出现的次数          for (int i = 0; i < T.size(); i++)expected_count[T[i]]++;                    int minWidth = INT_MAX, min_start = 0;//记录窗口大小，起点          int wnd_start = 0;          int appeared = 0;//          //不断向后扫描          for (int wnd_end = 0; wnd_end < S.size(); wnd_end++)          {              //如果当前元素在目标串中              if (expected_count[S[wnd_end]]>0)              {                  //相应元素出现次数加1                  appeared_count[S[wnd_end]]++;                  //注意appeared自增的条件                  if (appeared_count[S[wnd_end]] <= expected_count[S[wnd_end]])                      appeared++;              }              if (appeared == T.size())//完整的包含了一个目标串              {                  //录找最小串，如果记录的某元素的数量大于目标某元素的数量，                  //或者该元素在目标串中没有出现，则可以去掉一个                  while (appeared_count[S[wnd_start]] > expected_count[S[wnd_start]]                       || expected_count[S[wnd_start]]==0)                  {                      appeared_count[S[wnd_start]]--;                      wnd_start++;                  }                  //保留长度和起始位置                  if (minWidth > wnd_end - wnd_start + 1)                  {                      minWidth = wnd_end - wnd_start + 1;                      min_start = wnd_start;                  }              }          }          if (minWidth == INT_MAX)return " ";          else return S.substr(min_start, minWidth);      }