无重复字符最长子串----------------滑动窗口法

1.问题：给出一个字符串，找出其中无重复字符最长子串

　　abcbc　　最长无重复子串是abc  长度是3

 

2.方法一，暴力法

　　我们可以找出每一个子串，然后找到最长的无重复字符的子串就可了，方法简单粗暴。

　　代码如下：

　　

 1 #include<stdio.h>
 2 #include<string.h> 
 3 //判断有没有重复字符
 4 int isrepeat(char*str,int start,int end)
 5 {
 6     int i;
 7     for(i=start;i<end;i++)
 8     {
 9         if(str[i]==str[end])
10             return i;//如果找到重复的字符，返回该字符的索引 
11     }
12     return -1;//否则返回-1，表示没有重复字符 
13 }
14 
15 void findmaxsubstring(char * str)
16 {    
17     int i,j;
18     int n,m;//记录最长子串开始和结束的下标 
19     int max=0;//记录无重复字符子串最大长度 
20     int num=0;//当前无重复字符子串的长度 
21     int len=strlen(str);//求出字符串长度
22     //开始列举每一个子串 
23     for(i=0;i<len;i++)
24     {
25         for(j=i+1;j<len;j++)
26         {    
27             //判断从i开始到j之间有没有重复字符 
28             if(isrepeat(str,i,j)!=-1)
29             {    
30                 //如果有重复的字符 
31                 num=j-i;//记录当前的子串长度 
32                 if(num>max)
33                 {
34                     max=num;//记最大长度 
35                     n=i;//开始的下标 
36                     m=j-1;//结束的下标，因为第j个字符与前面有重复了 
37                 } 
38                 
39                 break;//有重复字符，结束本次循环 
40             }
41         }
42     }
43     //输出长度和该字符串 
44     for(i=n;i<=m;i++)
45         printf("%c",str[i]);
46     printf("\nthe max len is %d ",max);
47 }
48 
49 int main()
50 {
51     char * str="abcdefghacbcnnmjklabak";
52     findmaxsubstring(str);
53     return 0;
54 } 

算法分析，要遍历每一个子串，时间复杂度o(n^2),判断每一个子串是否有重复，时间复杂度o(n),

所以整个时间复杂度o(n^3)，这个复杂度是很高的，所以暴力法不合适。

3.方法二，滑动窗口

　　滑动窗口是一个在字符串处理中常用的方法，简单而言窗口就是一个自己维护的序列。对于字符串str而言，我们已经知道从

　　i 开始到 j  之间的字符串是没有重复字符的，那么从 i 到 j 就是一个窗口。下一步，我们要判断下一个字符 j+1 是否在窗口里重复了，如果没有重复

　　那么 j 滑动  j++  i 保持不变。如果重复了 i 滑动到重复字符的位置下一个位置，j 继续向前滑动 j++。这样当 j 走完就可以得到最长无重复子串。

　　这方法其实就是利用之前已知的信息进行判断，因为我们已知之前的子串有没有重复，在哪个位置重复了。

　　代码如下：

　　

 1 #include<stdio.h>
 2 #include<string.h> 
 3 //判断子串有么有重复字符 
 4 int isrepeat(char*str,int start,int end)
 5 {
 6     int i;
 7     for(i=start;i<end;i++)
 8     {
 9         if(str[i]==str[end])
10             return i;//如果找到重复的字符，返回该字符的索引 
11     }
12     return -1;//否则返回-1，表示没有重复字符 
13 }
14 
15 void findmaxsubstring(char *str)
16 {
17     int len=strlen(str);//得到字符串长度 
18     int max=0;//记录最大无重复子串长度 
19     int flag=0;// 
20     int i=0,j=1;
21     int num=1;//当前无重复子串长度 
22     int n,m;//记录最大无重复子串的开始，结束下标
23     // 
24     while(j<len)
25     {
26         flag=isrepeat(str,i,j);
27         if(flag==-1)//flag为-1没有重复字符 
28         {
29             j++;//j向前滑动 
30             num++;//当前无重复子串长度加一 
31         }
32         //有重复字符                            
33         else
34         {    
35             //如果当前长度大于最大长度 
36             if(num>max)
37             {    
38                 //记录下标 
39                 n=i;
40                 m=j-1;
41                 max=num;
42             
43             }
44             //i从有重复字符的下一个位置开始 
45             i=flag+1;
46             j++;//j继续向前滑动 
47             num=j-i;//当前无重复子串长度 
48             
49         }
50     }
51     //输出长度和该子串 
52     for(i=n;i<=m;i++)
53         printf("%c",str[i]);
54     printf("\nthe max len is %d ",max);
55 } 
56 int main()
57 {
58     char * str="abcdefghacbcnnmjklabak";
59     findmaxsubstring(str);
60     return 0;
61 } 

算法分析，滑动窗口是一遍过的，时间复杂度为o(n)，加上判断子串是否有重复的时间复杂度o(n)，所以

时间复杂度是o(n^2)。但其实很多时候判断子串是否有重复字符，不是用我上面的方法，而是用哈希表，或者集合，时间复杂度是o(1)

因此该方法的时间复杂度是线性的，实质为o(n）比暴力法好很多。