LeetCode (opens new window) 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

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

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

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


提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

源码 (opens new window)

思路： 使用滑动窗口，每次遇到重复字符，可以利用重复字符之后的窗口继续向后滚动，而不必从头计算。

所以需要一个能够记录出现过的字符下标的容器，这里因为字符范围有限定，所以使用长度128的数组即可。

为了防止数组初始值0与下标0重复，无法区分字符是否出现过，将数组中的值初始化为-1。

每次检查到重复字符出现，重新计算好滑动区间与长度，将排除滑动区间外的字符位置恢复成-1,。

public static int lengthOfLongestSubstring(String s) {
    if (s.length() == 0){
        return 0;
    }
    int maxLength = 1;
    int length = 1;
    int[] charIdx = new int[128];
    Arrays.fill(charIdx, -1);
    int i = 0;
    int j = 1;
    charIdx[s.charAt(0)] = 0;
    while ( j< s.length()) {
        int beginIdx = charIdx[s.charAt(j)];
        charIdx[s.charAt(j)] = j;
        if (beginIdx != -1){
            for (int k = i; k < beginIdx; k++) {
                charIdx[s.charAt(k)] = -1;
            }
            i = beginIdx+1;
            maxLength = Math.max(length, maxLength);
            length = j- beginIdx;
        }else {
            length++;
        }
        j++;
    }
    maxLength = Math.max(length, maxLength);
    return maxLength;
}

优化点：

1. 找到重复字符，重新划定滑动区间后，滑动区间外的字符对应的位置下标值其实不用恢复成-1，因为下次找到重复字符后，得到的下标值只有比滑动区间起始下标大，那么才是重复数值。

2. 数组也不用初始化为-1，为了与下标为0区分开，数组中存下标+1

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0){
        return 0;
    }
    int maxLength = 1;
    int length = 1;
    int[] charIdx = new int[128];
    int i = 0;
    int j = 1;
    charIdx[s.charAt(0)] = 1;
    while ( j< s.length()) {
        int beginIdx = charIdx[s.charAt(j)];
        charIdx[s.charAt(j)] = j+1;
        if (beginIdx >= i+1){
            i = beginIdx;
            maxLength = Math.max(length, maxLength);
            length = j- beginIdx+1;
        }else {
            length++;
        }
        j++;
    }
    maxLength = Math.max(length, maxLength);
    return maxLength;
}

优化：

1. 从下标0开始遍历，这样不用单独判断空字符串，代码更简洁

public static int lengthOfLongestSubstring(String s) {
    int maxLength = 0;
    int length = 0;
    int[] charIdx = new int[128];
    int beginIdx = 0;
    for (int k = 0; k < s.length(); k++) {
        int idx = charIdx[s.charAt(k)]-1;
        if (idx>=beginIdx){
            length = k-beginIdx;
            beginIdx = idx+1;
            maxLength = Math.max(length,maxLength);
            length = k-beginIdx;
        }
        length++;
        charIdx[s.charAt(k)] = k+1;
    }
    maxLength = Math.max(length, maxLength);
    return maxLength;
}