本文共 2586 字，大约阅读时间需要 8 分钟。

class Solution {//need2FT + hasFT + two pointer + count(check if satisfied)//O(n)public:	string minWindow(string S, string T) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		int lenT = T.size();		int lenS = S.size();		if(lenT <= 0 || lenT > lenS) return string("");//illegal input		int need2FT[256] = {0};		int hasFT[256] = {0};		for (int i = 0; i < lenT; ++i)//init need2FT 			need2FT[T[i]]++;		int start, end;//two pointer to sliding window		start = end = 0;		int count = 0;		int minStart, minEnd, minLen;		minLen = INT_MAX;		for ( ; end < lenS; ++end)		{			if(0 == need2FT[S[end]]) continue;//unrelated character			hasFT[S[end]]++;			if (hasFT[S[end]] <= need2FT[S[end]])				count++;			if (count == lenT)//maintain the minimum sliding window			{				while (hasFT[S[start]] > need2FT[S[start]] || 0 == need2FT[S[start]])				{					if(0 != need2FT[S[start]])						hasFT[S[start]]--;					start++;					if(start >= lenS)						break;				}				int newWinLen = end-start+1;				if (newWinLen < minLen)				{					minStart = start; 					minEnd = end;					minLen = newWinLen;				}			}			if(start >= lenS) break;					}		if(minLen == INT_MAX) return string("");		//then return the qualified sliding window		return S.substr(minStart, minLen);	}};

second time

class Solution {public:    string minWindow(string S, string T) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        vector
   
     cntTable(256, 0);        vector
    
      checkTable(256, 0);        for(int i = 0; i < T.size(); ++i) checkTable[T[i]]++;        //find the first window        int validCnt = 0;        int end;        for(end = 0; end < S.size(); ++end)        {            if(cntTable[S[end]] < checkTable[S[end]]) validCnt++;            cntTable[S[end]]++;            if(validCnt == T.size()) break;        }        if(end == S.size()) return "";        int minStart = 0;        while(minStart < S.size() && cntTable[S[minStart]] > checkTable[S[minStart]]) cntTable[S[minStart++]]--;        int minEnd = end;        //try to find a minimum one        int curStart = minStart;        for(int i = minEnd+1; i < S.size(); ++i)        {            cntTable[S[i]]++;            int newStart = curStart;            while(cntTable[S[newStart]] > checkTable[S[newStart]])            {                cntTable[S[newStart]]--;                newStart++;            }            curStart = newStart;            if(i-newStart < minEnd-minStart) minStart = newStart, minEnd = i;        }                return S.substr(minStart, minEnd-minStart+1);    }};
    
   

转载地址：http://wmxti.baihongyu.com/