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

示例 1:

输入: "abcabcbb"

输出: 3 

解释: 无重复字符的最长子串是 "abc"，其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

 

主要思想：“滑动窗口”，使用一个容器保存遍历的字符。

遍历字符串，同时将不重复的字符保存到窗口中，窗口的右边界加一，相当于向右滑动了一位；当遇到重复字符时，就从窗口的左边界缩小窗口大小，直到容器中不包括该重复字符。本质上也是借助外部空间。

 

解法1:

int lengthOfLongestSubstring(string s){    int n = s.size();    unordered_set
     
       set;    int max = 0, i = 0, j = 0;    while (i < n && j < n)    {        auto f = set.find(s.at(j));        if (f == set.end())        {            // 右边界向右滑动一位            set.emplace(s.at(j++));            max = std::max(max, j - i);        }        else        {            // 左边界向右缩小一位            set.erase(s.at(i++));        }    }    return max;}
     

 

解法2:

int lengthOfLongestSubstring(string s)    {        int n = s.size();        unordered_map
     
       mp;        int max = 0;        for (int j = 0, i = 0; j < n; ++j)        {            if (mp.count(s.at(j)) > 0)            {                // 直接将窗口的左侧缩小成重复的字符的下一位                i = std::max(mp.at(s.at(j)), i);            }            max = std::max(max, j - i + 1);            // 右边界向右滑动一位            mp.emplace(s.at(j), j + 1);        }        return max;    }