首页 > 代码库 > LeetCode--Minimum Window Substring
LeetCode--Minimum Window Substring
这题关键注意：T可能有重复，所以得统计次数，我之前理解错了，后来参考别人代码才知道的。
思路就是双指针+字符hash，具体见注释
1 class Solution { 2 public: 3 string minWindow(string S, string T) { 4 int data[260],i,j; 5 memset(data,0,sizeof(data)); 6 for(i=0;i<T.length();++i) 7 data[T[i]]++; 8 int now[260],left,right,minn=1<<29,num=0; 9 memset(now,0,sizeof(now)); 10 for(i=0,j=0;i<S.length();++i) 11 {
//这里的意思就是还没找到包含T所有字符的window的时候就增加右指针12 if(num<T.length()) 13 { 14 if(now[S[i]]<data[S[i]])num++; 15 now[S[i]]++; 16 }
//找到一个窗口17 if(num==T.length()) 18 {
//先把窗口前面的19 while(j<=i&&now[S[j]]-1>=data[S[j]]) 20 { 21 --now[S[j]]; 22 ++j; 23 } 24 if(minn>i-j+1)left=j,right=i,minn=i-j+1; 25 26 while(j<=i&&num==T.length()) 27 { 28 now[S[j]]--; 29 if(now[S[j]]<data[S[j]])num--; 30 ++j; 31 } 32 } 33 } 34 string temp; 35 if(minn<1<<29)return temp.assign(S,left,right-left+1); 36 else return ""; 37 } 38 };
http://blog.csdn.net/jellyyin/article/details/10313827
这个比较清晰，解释的。不需要用map，因为那样就成了O（nlogn）了
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。