无重复字符的最长子串

LeetCode第三题

题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

思路

1.暴力求解：
使用内外两个循环，遍历每个字符，再遍历其前面的所有字符，看是否有字符与之相等，得到不含重复字符的子串，子串长度即为所求。代码省略。
此暴力算法时间复杂度为n的平方，不需要额外存储空间，故空间复杂度为O（1）。

2.优化求解：
问题一：如何减少内循环的次数（当前字符与其之前的字符进行比较的次数）？
问题二：如何减少外循环的次数（子串的首字符滑动间隔）？

因为给定的是字符串，其中的字符能转换为ASCII码，范围在0~127。所以可以开辟一个大小为128的数组exist，元素下标为字符的ASCII值，内容为该字符在原字符串数组中的最新下标。当外循环检查某个字符时，判断该字符对应的exist数组中的值即可。这样就实现了对每个字符的内循坏，时间复杂度为O（1）。

针对外循环，可以将下一个子串的首字符下标设定为上一次比较相等的先前字符的原字符串下标加一。这样就实现了外循环的子串的首字符跳跃滑动。

源代码

int lengthOfLongestSubstring(char * s){
    int exist[128];         //建立一个存储字符是否出现的数组，对应下标为字符的ASCII码
    int max = 0;            //当前的最长子串的字符数
    int i = 0;              //子串的在S中的起始下标
    int sub = 0;            //下一次外循环的第一个待比较字符
    int cnt = 0;            //子串中不重复出现的字符数
    int j = 0;              //用来遍历的下标
    for(j = 0;j < 128;++j){
        exist[j] = -1;
    }
    while(1){
        for(j = sub;s[j];++j){
            if(exist[s[j]] == -1 || exist[s[j]] < i){
                exist[s[j]] = j;
                ++cnt;
            }
            else if(exist[s[j]] != -1 && exist[s[j]] >= i){
                i = exist[s[j]] + 1;
                exist[s[j]] = j;
                sub = j + 1;
                break;
            }

        }
        if(cnt > max)
            max = cnt;
        cnt = sub - i;
        if(!s[j])
            break;
    }
    return max;
}

时间复杂度为O（n），空间复杂度度为O（1）。