无重复字符的最长子串

来源：Leetcode第三题无重复字符的最长子串

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

示例 1:

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

同第一题一样习惯了暴力遍历，没有对时空复杂度上做过多的优化，官方解答没多少是C的，于是先找到了一个个人认为还不错的C的解答。
思路：同样是两层遍历，但是如果当剩下要遍历字符串的长度小于已求出的最长无重复子串时就没必要继续遍历了，其次，在内层循环遍历时，如果前面几位都不包含当前字符，则继续遍历，如果包含，就退出循环，计算下一个子串，采用的是滑动窗口的思想，遇到重复，左边i持续向右，直到不在重复，右边j再继续遍历字符串。C语言代码如下：

/**
* 字符串s前len位是否包含字符c
* return 0：不包含 1：包含
*/
int contains(char *s, char c, int len) {
    int i = 0;
    while(s[i] != NULL && i < len) {
        if(s[i] == c){
            return 1;
        }
        i++;
    }
    return 0;
}

int lengthOfLongestSubstring(char* s){
    int len = strlen(s);

    int i = 0;
    int j = 1;
    int maxLen = 0;
    // 如果从i位开始的字符串到末尾的长度小于最大字符串的长度，则不需要继续计算
    while(s[i] != NULL && (len - i > maxLen)) {
        while(s[j] != NULL && (contains( &s[i], s[j], j - i) == 0)) {
            // 遍历子串，如果前面几位都不包含当前的字符，则继续遍历；如果包含，则退出循环，计算下一个子串
            // 如果之前计算过的子串，则不继续计算
            // 例如，abcdabcd，当计算以首位开始的子串最长长度为abcd的字符串，因为bcd是abcd的子串，则不需要重复计算
            // 计算以b开头的子串时，直接判断上一次遍历j=4，即a是否属于bcd
            j++;
        }
        if(j - i > maxLen) {
            maxLen = j - i;
        }
        i++;
    }
    return maxLen;
}

官方解答有滑动窗口的进一步优化：

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。
也就是说，如果 s[j]在 [i, j)范围内有与 j’重复的字符，我们不需要逐渐增加i。我们可以直接跳过 [i，j’]范围内的所有元素，并将i变为j’ + 1。

但是为什么按照官方优化的方法，将左指针改成了j’ + 1之后反而在Leetcode上的运行时间会增加了呢？

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0 ){
        return 0;
    }
    char[] windows = new char[128];   //用于记录每个字符
    int left = 0 , right = 0 ;        //双指针控制窗口大小
    int maxlength = 0 ;               //记录窗口最大长度

    while(right< s.length()){
        char ch = s.charAt(right);     
        windows[ch]++; 

        //如果有重复字符则左边窗口一直加，直到剔除重复字符
        while (windows[ch] > 1){      
            char ch1 = s.charAt(left);
            windows[ch1]--;
            left++;
        }
        maxlength = Math.max(right - left+1 , maxlength);
        right++;
    }
    return maxlength;
}