找到字符串中不重复出现字符的最长子串长度

时间负责度最高的写法

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;
}