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 else34 { 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）比暴力法好很多。
联系客服
