滑动窗口算法(c语言讲义)滑动窗口算法主要用于解决与字符串检索相对应的题型。
算法的基本思路1 .辅助算法：快速指针
为了使用快捷的方针这一想法，在这里读者首先需要知道快捷的方针。
类型结构节点{ int data； 结构节点*下一步； }节点； 将head作为已创建的线性链表，k作为快指针，m作为慢指针； 节点*头、*k、*m； voidoutlink(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； 初始化结构体数组的voidinitmap(map*window ) {char ch； int i，count=0； for(I='a '； i='z '； I ) {Window[count].key=i； 窗口[ count ].count=0； //初始个数0} )主自定义函数intmaxlengthstring(char*s ) ) mapwindow(26 )； init map (窗口； //初始化int i； int left，right； int len=MIN； //初始化left=right=0； int temp； char ch2； //用于左窗体右移的判断； wile(rightstrlen(s ) ) {char ch=s[right]； ch2=ch； 光之美少女； //printf('%d '，len )； if () temp=need )窗口，ch )！=-1 ()//不重复的窗口[ temp ].count； len right-left (if ) {len=right - left； (else(/重复； wile (窗口[ needs (window，ch2 ) ].count！=0) {ch=s[left]； 左足； 窗口[ needs (window，ch ) ].count--； } }返回len； }指针right最初为0，以确保字符串从头到尾遍历，并创建临时变量ch以存储遍历的字符。 Need函数用于确定是否遍历了该ch字符的类型，如果遍历则返回-1，否则返回相应的下标。 用temp保存下标可以更容易地记录字符种类数。 每次窗口向右移动时更新len。
Need函数intneed(map*window，char ch ) )//定位函数，遍历搜索int i； for(I=0； i26； I ) if (窗口[ I ].key==ch ) if ) window[I].count==0) {return i； }else{return -1； }}}} Needs函数intneeds(map*window，char ch ) /下标({int i； for(I=0； i26； I () if ) window[I].key==ch ) {return i； }}找到当前最佳子字符串后，当窗口的左侧开始向右移动时，可以使用Needs在标签数组Window中查找支持left的字符的下标并标记该字符，以便于后续的遍历。
总结：必须确定右窗体向右放大的条件。 决定停止右表单向右放大、左表单向右缩小的条件。 选择适当的位置更新数据。 (我举的例子是在右表单移动时更新数据。 将其放入左窗体移动的代码中会有不同的效果)