前两天开始刷letcode，发现了这个题目。一开始看这个题目挺简单的，而且力扣上面也是中等难度，结果提交好几次都失败，最后看到一位题友写的，看了几遍才了每一步执行的意图。不得不惊叹别人思维是如此地灵动跳跃。

下面想分享出来，并再次理解一下。所有权归作者。未能征得作者许可，如有侵权请告知删除，这里仅想作为代码分析与欣赏之用。

代码是C语言格式的，其他语言可以做相应的转换。代码的整体思想是采用的滑动窗口，辅之以“哈希表”查找，利用空间换取时间。因此，在letcode提交中仅仅使用4ms，当然这跟字符串长度也是有关系的，但是时间上还是胜过了80%+的提交者。下面先看代码。

int lengthOfLongestSubstring(char * s){
    char flag[256] = {0,}; 
    char *left = s; char *right = s;
    int index = 0;
    int maxLen = 0, curLen = 0;
    int len = (int) strlen(s);

    if (len < 2) {
        return len;
    }

    while (right < s + len) {
        index = (int )(*right); //通过right指针取得当前字符的编码值
        if (1 == flag[index]) {//利用字符查表，判断是否出现过
            while (*left != *right) {
                curLen--;
                index =  (int )(*left);
                flag[index] = 0;
                left++;
            }

            left++;
        } else {
            curLen++;
            flag[index] = 1;
        }

        if (curLen > maxLen) {
            maxLen = curLen;
        }

        right++;
    }

    return maxLen;
}

解析：

首先定义一个256长度的字符数组用来记录字符串中的某个字符是否出现过，因为char*字符串中的字符的值为0~255，这个范围已经覆盖了ASCII字符集，而0为字符串结束符，因此256的长度是足够用来编码char*中所有可能的字符。数组初始化为0，当字符串中有一个之前没有出现过的字符时，将其置为1，使用flag[*s]去寻址相应的单元格，这里可以看作是哈希表的思想。

接着定义两个指针，分别为left, right，用于标识窗口的左右位置。

在搜索之前先排除字符串长度为0及1的情况，以免传入空字符导致后续取指针异常崩溃。而长度为1的时候则肯定不会有重复字符，因此长度小于2的字符串可以直接返回字符串长度作为无重复子串的长度。

然后开始一个while循环开始遍历字符串，循环结束条件为right指针指向了字符串的结尾。每循环一次，right指针向前行进一个字符长度。

在循环中，首先取得当前的字符，然后利用当前字符查flag表，如果当前字符在之前已经出现过，则查表得到的结果为1，否则为0。这是因为如果字符没有出现过我们就将其置为1，即if(1==flag[index])条件为假的时候，只需要将该位置置为1，再将cur_len（当前子串长度）加1。如果查表得到的是1，即之前已经出现过，则如果窗口左边的字符不同于右边的字符，则需要将左边移到和右边同一起点，且把其间出现过的字符全清0。如果窗口左右指针所指的字符是一样的，则只需要把左边往前行进一个字符即可。

if(1 == flag[index])中的while(*left != *right)起到什么作用呢？它的作用是当窗口右边出现了窗口中的字符时，需要将窗口左边边界移动至窗口中该字符之后。举个具体的例子来说明一下。例如有字符串“abcdaefggh”。最开始left，right都指向第一个字符“a”，然后滑动right直至字符串中间的“a”。此时left会指向b，最长的不重复字符串就是“bcda”，长度为4。而后right会继续前行至第二个“g”，此时left指向“b”,right指向第二个“g”，cur_len是“bcdaefg”的长度，值为7。由于right此时指向“g”已经在刚刚出现了一次，因此第一个“g”（包括第一个“g”字符）之前的任何字符再不可能与后面出现的字符形成不重复的子字符串了。因此需要将窗口左侧往右收缩，直至left指向第一个“g”,此时*left == *right，所以退出该循环。而后再执行left++，令其指向第二个“g”,所以，新的窗口左侧将从第二个“g”开始，并且，再次将right向右移动，循环此过程，直至right指向字符串尾。

整个过程中最长不重复子串长度使用max_len存储，当cur_len大于max_len的时候将新的cur_len赋给max_len。这样，max_len就能总是得到最大的子串长度。不过需要注意的一点处理是在内层while循环中有一个cur_len--，其作用是为了将子串长度清零以备后续新的子串计数用，此处完全可以直接置为初值。

至此，该算法就结束了，不得不感慨作者的思想真是太灵活了。以此作为学习记录一用。感谢作者！

转载请注明：OpenMind » 查找字符串中最长不重复的子字符串长度