滑动窗口算法（C语言描述）

第一种类型：不固定长窗口

问题1：***

C代码1：

#include<stdio.h>
#include<string.h>
#define N 5int min_len(int len1,int len2)
{return (len1 < len2 ? len1:len2);
}int main()
{int target = 0;int num[N];scanf("%d",&target);for(int i = 0;i < N;i++){scanf("%d",&num[i]);}//滑动窗口算法int left = 0;int right = 0;int sum = 0;int len = N+1;while(right < N){sum += num[right];while(sum >= target){sum -= num[left];if(sum < target){len = min_len(len,right-left+1);}left++;}right++;}if(len == N+1){printf("No such subarray exists!");}else{printf("%d",len);}return 0;
}

 问题2：*****

C代码2： 

#include<stdio.h>
#include<string.h>
#define N 80//向窗口右边添加一个字符，拓宽窗口
void Add_char(char ch,char *window)
{int right = strlen(window);window[right] = ch;
}
//检查窗口字符串是否满足包含字符串t所有字符且数量不少于t
int Is_ok(char *t,char *window)
{int needs[128]={0};int windows[128]={0};int n=0;int w=0;int len1 = strlen(window);int len2 = strlen(t);for(int i=0;i<len1;i++){w = (int)window[i];windows[w]++;}for(int j=0;j<len2;j++){n = (int)t[j];needs[n]++;}for(int k = 0;k < 128;k++){if(needs[k] != 0 && windows[k] < needs[k]){return 0;//不满足条件}}return 1;//满足条件
}/*判断当前满足条件的窗口字符串和满足条件的上一次结果字符串比较谁更短，并更新结果。
注意这里不要单纯的把指针result指向新结果（也就是窗口），因为窗口会随着循环而改变，
这样无法保留做中的正确结果，应该把结果字符串赋值给指针result指向的空间*/
void minlen(char *result,char *window)
{int result_len = strlen(result);int window_len = strlen(window);if(result_len > window_len){for(int i = 0;i <= window_len;i++){result[i] = window[i];}}
}//移除窗口左边第1个字符
void remove_char(char *window)
{int len = strlen(window);for(int i= 0;i < len;i++){window[i] = window[i+1];}
}int main()
{//定义所需字符数组char s[N];//存储字符串schar t[N];//存储字符串tchar window[N]={'\0'};//窗口内的字符串char *result = s;//存储找到的满足条件的最短字符串，这里初始化时将其指向字符串s//输入字符串s和tscanf("%s",s);scanf("%s",t);//定义滑动窗口所需变量int left = 0;//窗口左边界指针int right = 0;//窗口右边界指针int end = strlen(s);//字符串s的长度，窗口滑动的终止点//开始滑动窗口寻找满足条件的最短字符串int flag = 0;while(right < end){Add_char(s[right],window);//拓宽窗口右边界while(Is_ok(t,window)&&left < end)//窗口满足条件，已包含字符串t所有字符且数量也不少{flag = 1;minlen(result,window);//更新最短满足条件子串答案remove_char(window);//移除窗口左边第1个字符left++;//窗口左边界边界向前滑动}right++;}if(flag){printf("%s\n",result);}else{printf("No such string!\n");}return 0;
}

问题3：

C代码3：

和上面一个题目差不多，只不过在这里更新答案要加点条件。

#include<stdio.h>
#include<string.h>//向窗口右边添加一个字符，拓宽窗口
void add_char(int right,char *s,char *window)
{int len = strlen(window);window[len] = s[right];
}//检查窗口字符串是否满足包含字符串t所有字符且数量不少于t
int Is_ok(char *window,char *p)
{int len_w = strlen(window);int len_p = strlen(p);int windows[128]={0};int ps[128]={0};int t=0;for(int i = 0;i<len_w;i++){t = (int)window[i];windows[t]++;}for(int j = 0;j<len_p;j++){t = (int)p[j];ps[t]++;}for(int k = 0;k<128;k++){if(ps[k] != 0&& ps[k] > windows[k]){return 0;}}return 1;}//移除窗口左边第1个字符
void remove_char(char *window)
{int len_w = strlen(window);for(int i=0;i<len_w;i++){window[i] = window[i+1];}}
int main()
{//定义字符数组char s[20101]={'\0'};char p[20101]={'\0'};char win[20101]={'\0'};//输入字符串s和pscanf("%s",s);scanf("%s",p);//滑动窗口求解答案int left = 0;int right = 0;char *window = win;int end = strlen(s);int flag = 0;//检查s中满足条件的子字符串是否大于0int index_arr[1000]={0};int x = 0;while(right < end){add_char(right,s,window);while(Is_ok(window,p)&&left < end)字符串是异位字符串的前提1是两字符字符种类数量一样{int len1 = strlen(window);int len2 = strlen(p);if(len1==len2) //字符串是异位字符串的前提2是两字符字符长度一样{int flag2 = 0;for(int j=0;j<len1;j++){if(window[j] != p[j])//字符串是异位字符串的必要条件是两字符字符不能一模一样{flag2 = 1;}}if(flag2){index_arr[x] = left;x++;flag = 1;}}remove_char(window);left++;}right++;}if(flag){for(int i=0;i<x;i++){if(i != x-1){printf("%d ",index_arr[i]);}else{printf("%d\n",index_arr[i]);}}}else{printf("没有这样匹配的字符串！\n");}return 0;	
}

问题4：

C代码4：

和前面有一点不一样，主要是窗口移动不太一样。

#include<stdio.h>
#include<string.h>
#define N 80//向窗口右边添加一个字符，拓宽窗口
void Add_char(char ch,char *window)
{int right = strlen(window);window[right] = ch;
}
//检查窗口字符串是否满足包含字符串t所有字符且数量不少于t
int Is_ok(char *window)
{int windows[128]={0};int w=0;int len1 = strlen(window);for(int i=0;i<len1;i++){w = (int)window[i];windows[w]++;}for(int k = 0;k < 128;k++){if(windows[k] > 1){return 0;//不满足条件}}return 1;//满足条件
}/*判断当前满足条件的窗口字符串和满足条件的上一次结果字符串比较谁更短，并更新结果。
注意这里不要单纯的把指针result指向新结果（也就是窗口），因为窗口会随着循环而改变，
这样无法保留做中的正确结果，应该把结果字符串赋值给指针result指向的空间*/
void maxlen(char *result,char *window)
{int result_len = strlen(result);int window_len = strlen(window);if(result_len < window_len){for(int i = 0;i <= window_len;i++){result[i] = window[i];}}
}//移除窗口左边第1个字符
void remove_char(char *window)
{int len = strlen(window);for(int i= 0;i < len;i++){window[i] = window[i+1];}
}int main()
{//定义所需字符数组char s[N];//存储字符串schar window[N]={'\0'};//窗口内的字符串char result[N]={'\0'};//存储找到的满足条件的最短字符串，这里初始化时将其指向字符串s//输入字符串s和tscanf("%s",s);//定义滑动窗口所需变量int left = 0;//窗口左边界指针int right = 0;//窗口右边界指针int end = strlen(s);//字符串s的长度，窗口滑动的终止点//开始滑动窗口寻找满足条件的最短字符串int flag = 0;while(right < end){Add_char(s[right],window);//拓宽窗口右边界if(Is_ok(window)&&left < end)//窗口满足条件，已包含字符串t所有字符且数量也不少{flag = 1;maxlen(result,window);//更新最短满足条件子串答案}else{remove_char(window);//移除窗口左边第1个字符left++;//窗口左边界边界向前滑动}right++;}if(flag){printf("%d\n",strlen(result));}else{printf("No such string!\n");}return 0;
}