leetcode

主要参考：
【缓缓】使用「滑动窗口」即可简单求解 另附【算法框架】与【拓展题目】
我写了首诗，把滑动窗口算法变成了默写题

其实就是快慢指针的一种

什么是滑动窗口：对一个序列（本题是一个字符串s）使用双指针left、right，初始化left = right = 0，把索引左闭右开的区间[left,right)称为一个窗口（此处不适用双闭或双开是为了避免边界问题，左闭右开初始时区间[0,0)没有元素，让right向右移动一位区间[0,1)就包含元素0了）。

维护一个窗口，不断滑动，更新答案。

详细：

• 初始化双指针left和right。【初始化】

• 先不断增加right扩大窗口，直到窗口中的内容符合要求。【寻找可行解】

• 停止增加right，不断增加left缩小窗口，直到窗口中的内容不再满足要求。在每次增加left时都要更新所求的结果。【优化可行解】

• 不断重复扩大窗口、缩小窗口的操作，直到right到达序列的末端。【滑动窗口】

1. 在s中使用双指针left、right，初始化left = right = 0。

2. 先不断增加right扩大窗口，直到窗口中的字符串符合要求（包含p中的所有字符串）。【寻找可行解】

3. 此时停止增加right，转而不断增加left缩小窗口，直到窗口中的字符串不再符合要求（不包含t中的所有字符串了）。同时，每次增加left都要更新一轮结果。【优化可行解】

4. 重复第2步和第3步，直到right到达字符串的尽头。
   单字符串：

void slidingWindow(string s) {
    unordered_map window;//哈希表window 记录窗口中的字符
    int left=0, right=0;
    while(right < s.size()){
        char c=s[right];//c是将要移入窗口的字符
        right++;//增大窗口
        // 进行窗口内数据的一系列更新
        ...
              
        // 判断左侧窗口是否要收缩
        while(window needs shrink){
            char d = s[left];//d是将要移出窗口的字符
            left++;// 缩小窗口
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

双字符串：

vector findAnagrams(string s, string p) {
	vector res;//记录所求解
	unordered_map need;//哈希表need 记录需要凑齐的字符(一般为子串p）
	unordered_map window;//哈希表window 记录窗口中的字符 (维护一段长度为p.size()的窗口)
	for(auto c:p){//将p出现的所有元素放入哈希表need中
		need[c]++;
	}
	int valid=0;//表示window窗口中满足need条件的字符个数，如果valid和len(need)的大小相同，则说明窗口已满足条件
	int left=0,right=0;
        
	while(right
		char c=s[right];//c是将要移入窗口的字符
		right++;//增大窗口
		//进行窗口内数据的一系列更新
		...
            
		//判断左侧窗口是否要收缩(满足收缩窗口的条件)
		while(window needs shrink){
			char d=s[left];//d是将要移出窗口的字符
			left++;//缩小窗口
			//进行窗口内数据的一系列更新
			...
		}
	}
	return res;
}

注意：
执行if(need[c]) 即使不继续往下，也会导致 need中多出need[c]=0
最好改成if(need.count(c))

debug时迭代器使用：
参考：c++ map与unordered_map区别及使用

#include   
#include   
#include 

438. 找到字符串中所有字母异位词

class Solution {
public:
    vector findAnagrams(string s, string p) {
        //和 567：字符串的排列有点类似
        //异位词：字符频次相同 字符相同
        //哈希表 将p出现的所有元素放入哈希表中
        //维护一段长度为p.size()的窗口 
        //用valid表示窗口中已存在的p中的字符的数量
        unordered_map need;
        unordered_map window;
        vector res;
        for(auto c:p){
            need[c]++;
        }
        int valid=0;
        int left=0,right=0;
        while(right
            //增大窗口
            char c=s[right];
            right++;
            //判断当前进入窗口的字符是否是需要的字符 如果是则更新window中的对应情况
            if(need.count(c)){
                window[c]++;
                //若window中的这个字符数量已经满足需求 合法的字符数量valid增加1
                if(window[c] == need[c]){
                    valid++;
                }
            }
            //窗口内元素数量 >= p的字符个数 满足收缩窗口的条件
            while(right-left+1>p.size()){
                //判断是否满足结束条件，若满足则结束
                if(valid==need.size()){
                    res.push_back(left);
                }
                char d=s[left];
                left++;
                if(need.count(d)){
                    if(window[d]==need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return res;
    }
};

76. 最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map need;
        unordered_map window;
        for(auto c:t){
            need[c]++;
        }
        int valid=0;
        int left=0,right=0;
        int start=0,minlength=INT_MAX;
        while(right
            //增大窗口
            char c=s[right];
            right++;
            //判断当前进入窗口的字符是否是需要的字符 如果是则更新window中的对应情况
            if(need.count(c)){
                window[c]++;
                //若window中的这个字符数量已经满足需求 合法的字符数量valid增加1
                if(window[c]==need[c]){
                    valid++;
                }
            }
            //合法的字符数量 == 需要的字符个数 满足收缩窗口的条件
            while(valid==need.size()){
                //判断是否满足结束条件，若满足则结束
                if(right-left < minlength){
                    start=left;
                    minlength=right-left;
                }
                //缩小窗口
                char d=s[left];
                left++;
                if(need.count(d)){
                    if(window[d]==need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return minlength == INT_MAX ? "" : s.substr(start, minlength);
    }
};

567. 字符串的排列

class Solution {
public:
    bool checkInclusion(string t, string s) {
        unordered_map need;
        unordered_map window;
        for(auto c:t){
            need[c]++;
        }
        int valid=0;
        int left=0,right=0;
        int start=0,minlength=INT_MAX;
        while(right
            //增大窗口
            char c=s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]){
                    valid++;
                }
            }
            while(right-left >= t.size()){
                //判断是否满足结束条件，若满足则结束
                if(valid==need.size()){
                    return true;
                }
                //缩小窗口
                char d=s[left];
                left++;
                if(need.count(d)){ 
                    if(window[d]==need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return false;
    
    }
};