欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-12 18:43:12
1.问题:给出一个字符串,找出其中无重复字符最长子串 abcbc 最长无重复子串是abc 长度是3 2.方法一,暴力法 我们可以找出每一个子串,然后找到最长的无重复字符的子串就可了,方法简单粗暴。 代码如下: 1 #include 2 #include 3 // ......

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而言,我们已经知道从

  开始到 j  之间的字符串是没有重复字符的,那么从 i就是一个窗口。下一步,我们要判断下一个字符 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)比暴力法好很多。