解题思路
由于是求最短子串,很容易联想到使用滑动窗口去解决问题。可以按寻找合法子串->缩短子串->滑动窗口移动的思路进行解题。
(1)寻找合法子串:不使用哈希表,map等数据结构,而是使用三个计数数组。ct1统计s中字符出现次数,ct2统计t中字符出现次数,ct3标记“有效的包含”,其对单个字符进行统计,oks指t中出现的字符种类个数,ok是s中合法字符的种类个数。当s的子串s'有oks个合法字符,且每种字符的数量大于等于t中各字符的数量,则视为合法子串,接下来对该子串进行缩短。
(2)缩短子串:此时移动左指针,过滤掉s中从左指针处开始多于t中的字符,找到第一个字符数相等的位置,易知此时为最短子串位置。注意l要小于等于r这一条件,否则会越界。
(3)滑动窗口移动:ok数减1,清除ct3数组中的统计标志,ct1[s[l]]字符的计数减1,左右指针l和r同时自加,直到遍历完成。
变量名不太美观,如果可以的话跟着代码模拟一遍,注意括号内条件。
代码
1 class Solution { 2 public: 3 string minWindow(string s, string t) { 4 int n1=s.size(),n2=t.size(); 5 string ans; 6 if(n1<n2) 7 return ans; 8 9 int ct1[130]={0},ct2[130]={0},ct3[130]={0}; 10 11 int oks=0; 12 for(int i=0;i<n2;++i) 13 { 14 if(ct2[t[i]]==0) ++oks; //统计有几类字符 15 ++ct2[t[i]]; 16 } 17 18 int l=0,r=0,ok=0,i; 19 int flag=1,minN=100010,temp,pos; 20 char tc; 21 while(r<n1&&l<=r) 22 { 23 tc=s[r]; 24 ++ct1[tc]; 25 if(ct2[tc]&&!ct3[tc]&&ct1[tc]==ct2[tc]) //对t中存在的字符进行比较,若相等则ok数+1 26 { 27 ++ok; 28 ct3[tc]=1; //重复则不计数 29 } 30 31 if(ok==oks) 32 { 33 if(!flag) 34 flag=1; 35 36 tc=s[l]; 37 while(ct1[tc]>ct2[tc]&&l<=r) //找到s和t第一个相等个数字符的位置 38 { 39 --ct1[tc]; 40 ++l; 41 tc=s[l]; 42 } 43 44 temp=r-l+1; 45 if(temp<minN) //更新长度 46 { 47 minN=temp; 48 pos=l; 49 } 50 51 --ct1[tc]; 52 --ok; 53 ct3[tc]=0; 54 ++l; //计数少1,清除重复标记,左指针向右移动 55 } 56 ++r; //右指针移动,滑动窗口向右扩展 57 } 58 59 if(flag) //存在结果则更新ans 60 ans=s.substr(pos,minN); 61 return ans; 62 } 63 };