無重復(fù)字符最長子串----------------滑動窗口法

Coder編程 2020-05-31

展開全文

1.問題：給出一個字符串，找出其中無重復(fù)字符最長子串

　　abcbc　　最長無重復(fù)子串是abc 長度是3

2.方法一，暴力法

　　我們可以找出每一個子串，然后找到最長的無重復(fù)字符的子串就可了，方法簡單粗暴。

　　代碼如下：

 1 #include<stdio.h>
 2 #include<string.h> 
 3 //判斷有沒有重復(fù)字符
 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;//如果找到重復(fù)的字符，返回該字符的索引 
11     }
12     return -1;//否則返回-1，表示沒有重復(fù)字符 
13 }
14 
15 void findMaxSubString(char * str)
16 {    
17     int i,j;
18     int n,m;//記錄最長子串開始和結(jié)束的下標(biāo) 
19     int max=0;//記錄無重復(fù)字符子串最大長度 
20     int num=0;//當(dāng)前無重復(fù)字符子串的長度 
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(luò)之間有沒有重復(fù)字符 
28             if(isRepeat(str,i,j)!=-1)
29             {    
30                 //如果有重復(fù)的字符 
31                 num=j-i;//記錄當(dāng)前的子串長度 
32                 if(num>max)
33                 {
34                     max=num;//記最大長度 
35                     n=i;//開始的下標(biāo) 
36                     m=j-1;//結(jié)束的下標(biāo)，因為第j個字符與前面有重復(fù)了 
37                 } 
38                 
39                 break;//有重復(fù)字符，結(jié)束本次循環(huán) 
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 }

算法分析，要遍歷每一個子串，時間復(fù)雜度O(n^2),判斷每一個子串是否有重復(fù)，時間復(fù)雜度O(n),

所以整個時間復(fù)雜度O(n^3)，這個復(fù)雜度是很高的，所以暴力法不合適。

3.方法二，滑動窗口

　　滑動窗口是一個在字符串處理中常用的方法，簡單而言窗口就是一個自己維護的序列。對于字符串str而言，我們已經(jīng)知道從

　　i 開始到 j 之間的字符串是沒有重復(fù)字符的，那么從 i 到 j 就是一個窗口。下一步，我們要判斷下一個字符 j+1 是否在窗口里重復(fù)了，如果沒有重復(fù)

　　那么 j 滑動 j++ i 保持不變。如果重復(fù)了 i 滑動到重復(fù)字符的位置下一個位置，j 繼續(xù)向前滑動 j++。這樣當(dāng) j 走完就可以得到最長無重復(fù)子串。

　　這方法其實就是利用之前已知的信息進行判斷，因為我們已知之前的子串有沒有重復(fù)，在哪個位置重復(fù)了。

　　代碼如下：

 1 #include<stdio.h>
 2 #include<string.h> 
 3 //判斷子串有么有重復(fù)字符 
 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;//如果找到重復(fù)的字符，返回該字符的索引 
11     }
12     return -1;//否則返回-1，表示沒有重復(fù)字符 
13 }
14 
15 void findMaxSubString(char *str)
16 {
17     int len=strlen(str);//得到字符串長度 
18     int max=0;//記錄最大無重復(fù)子串長度 
19     int flag=0;// 
20     int i=0,j=1;
21     int num=1;//當(dāng)前無重復(fù)子串長度 
22     int n,m;//記錄最大無重復(fù)子串的開始，結(jié)束下標(biāo)
23     // 
24     while(j<len)
25     {
26         flag=isRepeat(str,i,j);
27         if(flag==-1)//flag為-1沒有重復(fù)字符 
28         {
29             j++;//j向前滑動 
30             num++;//當(dāng)前無重復(fù)子串長度加一 
31         }
32         //有重復(fù)字符                            
33         else
34         {    
35             //如果當(dāng)前長度大于最大長度 
36             if(num>max)
37             {    
38                 //記錄下標(biāo) 
39                 n=i;
40                 m=j-1;
41                 max=num;
42             
43             }
44             //i從有重復(fù)字符的下一個位置開始 
45             i=flag+1;
46             j++;//j繼續(xù)向前滑動 
47             num=j-i;//當(dāng)前無重復(fù)子串長度 
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 }