滑动窗口算法（C语言讲解）
滑动窗口算法主要用于解决字符串查找对应排序的题型。
算法的基本思路
1.辅助算法 :快慢指针
由于要运用快慢指针的思想，这里读者需要先了解快慢指针。
typedef struct node{int data;struct node *next;}Node;//设head为已创建好的线性链表,k为快指针, m为慢指针;Node * head, *k, *m;void OutLink(Node *head){Node *k, *m;k = head->next->next;//每次走两个next; m = head->next;//每次走一个next; }
因快慢指针的特性，我们常常可以用它来判断链表是否存在环。
如果能够理解快慢指针那今天的这个算法你也就解决了。
2.主算法 :滑动窗口
滑动窗口顾名思义就是以窗口的形式进行移动查找。
先看题目: 输入字符串S,请从S查找到最长无重复字母的子串的长度。(例 ：S = "abcdbgf", 输出 : 4)
如果使用暴力算法的话时间复杂度为O(N^2),显然效率很慢。
由于是查找最值所以我们需要对字符串进行遍历查找,在遍历循环的过程我们需要两个指针right，left，将right,keft初始化为0。(注：此指针并非C语言的指针,该指针表示字符数组的下标指针)，通过指针right我们可以遍历查找到最长对应要求的子串长度(遍历到存在重复字母种类为止),如果运气好在right的后续遍历中不存在更优的子串那它就是最终答案，运气不好的话后续的遍历可能就存在更优的子串，为了保证找到最长的子串我们还需要对剩下的字符串进行遍历查找，看是否能找出跟优的子串，这时需要left去遍历S(左窗体的右移)，遍历到遇到重复字母的下标为止(跳过找到的子串，向后遍历)，以此循环直到right遍历完S字符串。
解决函数如下:
首先需要定义结构体Map用于记录26个字母各自出现的个数
typedef struct{char key;//字母int count;//出现个数}Map;
还需要对结构体数组进行初始化
void InitMap(Map *Window){char ch;int i, count = 0;for(i='a';i<='z';i++){Window[count].key = i;Window[count++].count = 0;//初始个数为0}}
主自定义函数
int MaxLengthString(char *s){Map Window[26];InitMap(Window);//初始化;int i;int left, right;int len = MIN;//初始化; left = right = 0;int temp;char ch2; //用于左窗体的右移的判断;while(right<strlen(s)){char ch = s[right];ch2 = ch;right++;//printf("%d ",len);if((temp = Need(Window,ch))!=-1){//没重复; Window[temp].count++;if(len<right - left){len = right - left;}}else{//重复了;while(Window[Needs(Window,ch2)].count!=0){ch = s[left];left++;Window[Needs(Window,ch)].count--;}}}return len;}
指针right开始时为0,保证字符串从头遍历到尾,创建临时变量ch存储遍历到的字母,Need函数用于判断该ch字母的种类是否遍历到过,如果遍历过就返回-1，否则就返回对应的下标。并用temp存储下标便于字母种类个数的记录。在每次窗口向右移动时更新len。
Need函数
int Need(Map *Window,char ch){//定位函数,遍历查找int i;for(i=0;i<26;i++){if(Window[i].key==ch){if(Window[i].count==0){return i;}else{return -1;}}}}
Needs函数
int Needs(Map *Window,char ch)//查找下标{int i;for(i=0;i<26;i++){if(Window[i].key==ch){return i;}}}
找到当前最优子串后，窗口的左侧要开始向右移动时用Needs查找left对应字母在标记数组Window中的下标，对其字母去标记便于后续遍历。
