無重復字符最長子串----------------滑動視窗法

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）比暴力法好很多，

標籤：C

上一篇：[題記]生命游戲-leetcode

下一篇：C 實戰練習題目5