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 else34 { 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 }
算法分析，滑動窗口是一遍過的，時間復(fù)雜度為O(n)，加上判斷子串是否有重復(fù)的時間復(fù)雜度O(n)，所以
時間復(fù)雜度是O(n^2)。但其實很多時候判斷子串是否有重復(fù)字符，不是用我上面的方法，而是用哈希表，或者集合，時間復(fù)雜度是O(1)
因此該方法的時間復(fù)雜度是線性的，實質(zhì)為O(n）比暴力法好很多。
