滑动窗口类问题框架

初始化窗口端点L，R，一般L为0，R为1
    初始化最优值
    while R < len(Array):
        while R < len(Array):
            R += 1              #移动右端点
            if R < len(Array):
                更新状态        
            if 状态满足条件:
                可选的更新最优值的位置
                break           #一旦满足条件即跳出
        if R == len(Array):     # 若循环是由于移动到数组末尾结束，则停止整个程序。因为之后已经不再有可能的解
            break
        while L < R:
            更新状态    # 移动左端点，需要更新状态
            L += 1
            if 状态满足条件：
                可选的更新最优值的位置
            else：  # 一旦窗口所在区间不再满足条件即跳出，去移动右端点
                break
        可选的对于L，R端点的后续处理
    return 最优值

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int minWindows(string s, string target){
	int left = 0, right = 0，step= INT_MAX;
	unordered_map<char, int> um_tar;
	
	bool stop = true;
	
	//记录目标字符串
	for(char c:target){
		um_tar[c]++;
	}
	
	//找到第一组字符串
	while(right < s.size()){
		stop = true;
		if(um_tar.find(s[right]) != um_tar.end()){
			um_tar[s[right]]--;	
		
			for(unordered_map<char, int>::iterator it = um_tar.begin();it != um_tar.end();it++){
				if((*it)->second()>0){
					stop = false;
				}
			}
			//如果找齐了
			if(stop){
				step = min(step, right-left);
				
				//可以开始左指针移动了
				while(left<right){
					if(um_tar.find(s[left]) != um_tar.end()){
						um_tar[s[left]]++;
						if(um_tar[s[left]] > 0){
							break;
						}
							
					}
					left++;
				}
			}
		}
		right++;
	}
}

#include<iostream>
#include<string>

/*
int maxSize(std::string s1,std::string s2){
	int sz1 = s1.size(), sz2 = s2.size();
	
	int max = 0;
	int ptr = 0;
	
	while(ptr<sz1 - max){	//如果把s1剩下的都整上都不够的话就没必要了
		for(int i = 0;i<sz2 - max;i++){	//如果把s2剩下的都整上都不够，就没必要了吧
			//当碰到可以匹配的时候
			if(s1[ptr] == s2[i]){
				int temp1 = ptr, temp2 = i;
				//开始匹配
				while(temp1<sz1 && temp2<sz2 && s1[temp1] == s2[temp2]){
					temp1++;
					temp2++;
				}
				//匹配完毕，更新长度
				max = max(max, temp1-i+1);
			}
		}
		
		ptr++;
	}
}
*/

//解法2：
/*
	如果对长串做一个哈希分析，短串就不用去滑动了
*/
#include<unordered_map>

//s1短，s2长
int maxSize(std::string s1, std::string s2){
	int sz1 = s1.size(), sz2 = s2.size(), max_ = 0;
	
	//构建长串哈希表
	unordered_map<char, vector<int>> um_s;
	for(int i = 0;i<sz2;i++){
		um_s[c].push_back(i);
	}
	
	//开始短串匹配
	for(int j = 0;j<sz1 - max_;j++){
		vector<int> temp
		//如果有这个字符，就开始匹配
		if(um_s.find(s1[j])!=um_s.end()){
			temp = um_s[s1[j]];
			for(int i:temp){
				if(i > sz2 - max_){
					break;	//没必要了，后面都没必要了
				}
				else{
					pass;
					//匹配算法，电脑没电了不写了。
				}
			}
		}
	}
}