本文共 994 字，大约阅读时间需要 3 分钟。

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

示例 1:

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

示例 2:

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

示例 3:

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

思路：

1、采用哈希表m记录每个字符最后出现的位置，用一个for循环O(n)的时间复杂度来解决。

2、设置左滑动指针l，记录当前要找的不重复子串的左端点位置。每当出现重复字符的时候，比较一下该字符最后出现的位置m[s[i]]与左滑动指针l谁在前面，如果字符在前面就不管了，如果要是左滑动指针在前面的话，这个时候就要将左滑动指针指向该字符最后出现位置的下一个位置，同时更新最大长度，最大长度是i与l之间的那一段。

3、另外需要注意一下别忘了最后那一段不重复子串的长度。

时间复杂度O(n), 空间复杂度是O(n)， 额外开辟内存空间O(1)。

PS：空间复杂度是和额外开辟的内存空间是两回事：前者指写入了多少内存，后者指额外占用的内存大小。处理字符串问题的时候只要不涉及其他语言，普遍都是ascii不管数字符号大小写字母空格啥的……所以针对字符的hash基本就是直接用ascii码作为哈希值，ascii的hash空间非常小只有128个int，相对于字符串的空间都非常小。

class Solution {public:    int lengthOfLongestSubstring(string s) {        int i=0, l=0, len=0;        unordered_map
   
    m;        for(; i
    
     =l){                len=max(len, i-l);                l=m[s[i]]+1;            }            m[s[i]]=i;        }         len=max(len, i-l);        return len;    }};
    
   

转载地址：http://rqabi.baihongyu.com/