时间负责度最高的写法
int contans(char* s,int begin,int end,char p){
for (int i=0; i<=end-begin; i++){
if (s[i+begin] == p){
return 1;
}
}
return 0;
}
int lengthOfLongestSubstring(char* s) {
int count = 0;
if (strlen(s) == 1 ){
return 1;
}
for (int i=0; i<strlen(s); i++){
for (int j=i+1; j<strlen(s); j++){
if (contans(s,i,j-1,s[j]) == 1){//判断前面的一段数组中是否包含字符
if (count < j-i){
count = (j-i);
}
break;
}else if (j == strlen(s)-1){//到了最后
if (count < j-i+1){
count = (j-i+1);
}
}
}
}
return count;
}
我擦我发现LeetCode都崩了，输入了一个上千行的字符。
image.png
正解如下，创建一个哈希表用于记录字符串中字符的位置，key为字符value为该字符在字符串中的位置。
int lengthOfLongestSubstring(char* s) {
int begin =0;//记录子串的起始位置
int end = 0;//记录子串的结束位置
int i = 0;//记录当前不重复字符串的起点
int j = 0;//记录当前不重复字符串的终点
int max = 0;
int hs[128] = {};
int k = 0;
while (k<128){
hs[k] = -1;
k++;
}
while (i<strlen(s)){
if (hs[s[i]-0] >= j){//如果字符串出现了对应的位置且大于j，说明有遇到了重复的字符。
j = hs[s[i]-0] + 1;
}else{//如果小于等于j，说明是第一次出现，无重复的，
if (max < i-j+1){
max = i-j+1;
}
}
hs[s[i]-0] = i;
i++;
}
return max;
}
