题解 | #最小覆盖子串#

char* minWindow(char* S, char* T ) {
    /*hash T字符串*/
    char T_hash[256] = {0};
	int i=0,j=0;
	while(T[i] != '\0'){
		T_hash[T[i++]]++;
	}
	/*把T字符串中出现过的单词按顺序排列*/
	char T_word[100] = {0};
	for(i=0;i<256;i++){
		if(T_hash[i] != 0)
			T_word[j++] = i; 
	}
	/*
    滑动窗口比较，双指针
    XDOYE，左指针不动，右指针后移；当XDOYEZ时，右指针不动，左指针后移；
    左指针后移一位变成DOYEZ，此时match != 3，右指针后移
    */
	int T_Long = j,left = 0,right = 0,match = 0;
	char window[256] = {0};
	int width=0,minwidth = strlen(S)+1;
	static char res[2000]={0};//一定要用static，2000太大
	while(S[right] != '\0'){
		window[S[right++]]++;
		match = 0;
		for(i=0;i<T_Long;i++){
			if(window[T_word[i]]-T_hash[T_word[i]]>=0)
				match++;
			else match--;
		}
		while(match == T_Long){
			width = right-left;
			if(minwidth > width){
				minwidth = width;
				memset(res,'\0',sizeof(res));
				for(i=0,j=left;j<right;i++,j++){
					res[i] = S[j];
				}
				res[i]='\0';
			} 
			window[S[left++]]--;
			match = 0;
			for(i=0;i<T_Long;i++){
				if(window[T_word[i]]-T_hash[T_word[i]]>=0)
					match++;
				else match--;
			}
		}
	}
    return res;
}