数组

¶长度最小的子数组

/* 过了，但是很low */
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> tcnt;
        unordered_map<char, int> scnt;
        int m = s.size(), n = t.size();
        for (int i = 0; i < n; i++) tcnt[t[i]]++;
        int startIndex = 0, endIndex = 0;
        int newSize = INT32_MAX;
        int windowSize = 0;
        string subStr;
        for (; endIndex < m; endIndex++) {
            if (tcnt.find(s[endIndex]) != tcnt.end()) {
                scnt[s[endIndex]]++;
                bool flag = true;
                for (auto it = tcnt.begin(); it != tcnt.end(); it++) {
                    if (scnt.find(it->first) == scnt.end() || scnt[it->first] < it->second) {
                        flag = false; break;
                    }
                }
                if (flag) {
                    while (startIndex <= endIndex) {
                        if (tcnt.find(s[startIndex]) == tcnt.end()) startIndex++;
                        else if (scnt[s[startIndex]] > tcnt[s[startIndex]]) {
                            scnt[s[startIndex]]--; startIndex++;
                        }
                        else break;
                    }
                    windowSize = endIndex - startIndex + 1;
                    if (windowSize < newSize) {
                        newSize = windowSize;
                        subStr = s.substr(startIndex, windowSize);
                    }
                    scnt[s[startIndex]]--; 
                    if (scnt[s[startIndex]] == 0) scnt.erase(s[startIndex]);
                    startIndex++;
                }
            }
        }
        return subStr;        
    }
};

/* 思路是这样：
* 创建两个哈希表
* 用其中一个把 t 串中的字符统计一下
* 另一个代表 s 串中与 t 串相同的那些字符在滑动窗口中的个数（没有不是 0，要 erase 掉）
* 然后用滑动窗口过一遍
* 窗口：满足是覆盖字串，但不保证是最小
* 起始位置移动：
* 1. 找到满足条件的子串时，为保证是当前最小，把串从起始位置开始的多余部分剪掉
* 剪的同时要同步更新代表滑动窗口中字符状态的哈希表
* 此时起始位置一定会移动到一个在 t 串中也有的字符的位置
* 2. 在确定成功找到一个子串后，向前移动一个位置
* 结束位置移动：
* 窗口的结束位置就是遍历 s 的指针即 for 循环里的索引
* 结束位置每向前移动一次，更新哈希表，判断当前字串是否满足“覆盖”的条件
* 满足“覆盖”，再考虑“最小”（可行解到局部最优解）
*/

LeetCode 滑动窗口演示

/* 
* 考虑优化，s 串中的无关字符使得我们做了一些无用操作
* 我们实际只关心 t 串中出现的字符
* 那么可以先预处理 s 串，丢掉 s 串中在 t 串没有出现的字符
* 再做滑动窗口
*/

/* 先预处理 s 串，压缩存储 */
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> tcnt;
        vector<int> matchS; string newS;
        int m = s.size(), n = t.size();
        for (int i = 0; i < n; i++) tcnt[t[i]]++;
        for (int i = 0; i < m; i++) {
            if (tcnt.find(s[i]) != tcnt.end()) {
                newS += s[i];
                matchS.push_back(i);
            }
        }
        int newSLength = newS.size();
        int startIndex = 0, endIndex = 0;
        unordered_map<char, int> wcnt;
        int windowLength = 0;
        int newSize = INT32_MAX;
        string subStr;
        for (; endIndex < newSLength; endIndex++) {
            wcnt[newS[endIndex]]++;
            bool flag = true;
            for (auto it = tcnt.begin(); it != tcnt.end(); it++) {
                if (wcnt.find(it->first) == wcnt.end() || wcnt[it->first] < it->second) {
                    flag = false; break;
                }
            }
            if (flag) {
                while (wcnt[newS[startIndex]] > tcnt[newS[startIndex]]) {
                    wcnt[newS[startIndex]]--; startIndex++;
                }
                windowLength = matchS[endIndex] - matchS[startIndex] + 1;
                if (windowLength < newSize) {
                    newSize = windowLength;
                    subStr = s.substr(matchS[startIndex], windowLength);
                }
                wcnt[newS[startIndex]]--;
                if (wcnt[newS[startIndex]] == 0) wcnt.erase(wcnt[startIndex]);
                startIndex++;
            }
        }
        return subStr;
    }      
};

/* 
* 自己写的逻辑自己看着舒服一些
* 所以也不想看题解了
* 贴一个评论区模板在这里
*/

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (char c : t.toCharArray()) 
        need.put(c,need.getOrDefault(c,0)+1);
	int left = 0, right = 0;
	int valid = 0; 
	while (right < s.size()) {
    	// c 是将移入窗口的字符
   	 	char c = s.charAt(right);
    	// 右移窗口
    	right++;
    	// 进行窗口内数据的一系列更新
    	...

    	/*** debug 输出的位置 ***/
    	System.out.println("window: ["+left+","+ right+")");
    	/********************/
    
    	// 判断左侧窗口是否要收缩
    	while (window needs shrink) {
        	// d 是将移出窗口的字符
        	char d = s[left];
        	// 左移窗口
        	left++;
        	// 进行窗口内数据的一系列更新
        	...
    	}
	}
}