题目描述

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

样例

示例 1:

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

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

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

算法1

(暴力枚举) $O(n^2)$

用一个大小为128的数组做哈希表，将i作为字符串的结尾，j作为字符串的开头的前一个字母，j向前探，直到出现重复字符为止。
因为ascii码表的长度为128，所以如果字符中只有英文字母或者符号的话128就足够了，不需要特殊处理大小写。

时间复杂度

$ O(n^2) $

参考文献

C++ 代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i, j, ans = 0;
        int n = s.size();
        for(i = 0; i<n; i++){
            vector<int> st(128, 0);//数组长度为128，ascii码表长度
            for(j = i; j>=0; j--)
                if(st[s[j]]++) break;//出现重复字符
            ans = max(ans, i - j);
        }
        return ans;
    }
};

算法2

(滑动窗口) $O(n)$

i与上一方法一致，同样指向结尾子串的结尾处，而j则指向开头处，即子串第一个字符。这里利用的是i和j的单调性，如果i向后移动一位，那么j则不动或者向后移动。因为i向后移动代表子串延长了一位，如果新的字符是原子串中出现过的字符，那么就将j向后移动，直到遇到同样的字符将其删去即可。如果新的字符是原子串中没有出现过的字符，那么j就不用移动。由此可以看到i和j是具有单调性的。

时间复杂度

$O(n)$

参考文献

C++ 代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i, j, ans = 0;
        int n = s.size();
        vector<int> st(128, 0);
        j = 0;
        for(i = 0; i<n; i++){
            st[s[i]]++;
            while(st[s[i]] > 1){
                st[s[j]]--;
                j++;
            }
            ans = max(ans, i - j +1);
        }
        return ans;
    }
};

算法3（滑动窗口）

与上一个算法不同之处在于哈希表存放的是每个字母最后出现的位置。这样如果i后移，更新一个元素，那么我们就考虑是否需要更新j的值。
在哈希表中存放的是每个字母最后出现的位置，那么就比较j与哈希表中新元素对应的最后出现的位置st[s[i]]，如果这个位置大于等于j，代表新元素在原子串中是重复的，就更新值显然要令j = st[s[i]] + 1。如果这个位置小于j，则代表这个新元素在原子串中是没有的，就不更新值。
综上得到一个公式 j = max(j, st[s[i]] + 1);

时间复杂度

O(n)

C++代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i, j, ans = 0;
        int n = s.size();
        vector<int> st(128, -1);
        j = 0;
        for(i = 0; i<n; i++){
            j = max(j, st[s[i]] + 1);
            st[s[i]] = i;//更新位置
            ans = max(ans, i - j +1);
        }
        return ans;
    }
};

需要注意的是st数组的初始值要设置为-1，代表没有出现过，-1+1 = 0 <=j 不会干扰j的更新。
而且要先更新j的坐标，然后在更新哈希表中的位置坐标