求无重复字符的最长子串

题目描述：

输入: s = "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"

，所以其长度为 3。

    请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

数据范围 ：

• 0 <= s.length <= 5 * 104

思路：根据这个题的数据范围，不可能做到O(n^2),所以考虑遍历一次或者里面加一个二分。 遍历的话那么容易想到双指针来做，用i和j来维护一个区间，这个区间的所有元素都只出现过一次。

     遍历到i的时候，如果此时j--i有相同的字符，也就是s[i]==s[j]的时候，以i结尾的子串符合条件的最大长度是多大呢？答案的左区间一定在j的右边，为什么？因为如果最后的答案的区间的左边界在j的左边，那么还是没有改变在目前维护区间存在s[i]==s[j]的事实。

     也就是说，如果遇到s[i]==s[j],我们只需要j++，也就是缩小左边界，直到mp[i]==1.再更新一次答案，目前维护的区间的长度为i-j+1，与上一个答案求最大值就行了。 为什么答案一定正确？因为遍历了每一个s[i]作为答案的右区间的可能。

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> mp;//哈希每个元素出现的次数
        int ans=0;
        for(int i=0,j=0;i<s.size();i++){
            mp[s[i]]++;
            while(mp[s[i]]>1&&j<=i){
               // cout<<j<<" "<<i<<endl;
                mp[s[j]]--;
               j++;
            }
            
            ans=max(ans,i-j+1);//更新答案
        }
        return ans;
    }
};