一、问题描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
题目链接：无重复字符的最长子串
二、题目要求
样例 1
输入: s="abcabcbb"输出: 3解释: 因为无重复字符的最长子串是"abc"，所以其长度为3。
样例 2
输入: s="bbbbb"输出: 1解释: 因为无重复字符的最长子串是"b"，所以其长度为1。
考察
字符串、滑动窗口 建议用时20~35min
三、问题分析
拿到这一题，首先确定属于字符串的应用，以样例 1为例，我一开始的思路是：
从字符串逐个开始遍历，依次向后寻找以当前字符作为首位的最大子串。
abcabcbb第一位aabc第二位bbca第三位ccab第四位aabc...... 最后一位bb
我一开始的想法是哈希表（C++的map计数），如果当前这个字符前面的哈希表里面没有出现，那么字符串长度+1，这个字符哈希表+1。按照上面的步骤，逐步遍历。
但是这种算法效率也太差了，我们优化一下。
其实可以把原来的二层循环简化到一层，l r作为双指针分别指向第一个字符，依次向后遍历。
如果r指向字符没出现，将它后一位的下标加入哈希表中，l不变，r++。
如果r指向字符出现，l需要变成上一个出现的字符后一位，这样可以保障[l,r]区间内不存在重复的字符。
可以依照力扣上面的几张图示，帮助理解。
四、编码实现
1.优化前
classSolution { public: intlengthOfLongestSubstring(strings) { inti,j,n=s.size(),ans=0,k=0;//初始化代码map<char,int>m;//哈希表存储for(i=0;i<n;i++)//每一个字符作为起点 { m.clear();//清空ans=0;//for(j=i;j<n;j++)//向后寻找无重复字符 { if(m[s[j]]==0)//找到了 { ans++;//计数m[s[j]]++;//标记 } else//没找到直接退出break; } k=max(k,ans);//寻找最大值 } returnk;//输出结果 } };
2.优化后
classSolution { public: intlengthOfLongestSubstring(strings) { intl,r,n=s.size(),ans=0;//初始化变量map<char,int>m;//哈希表for(l=0,r=0;r<n;r++)//区间移动 { if(m[s[r]]>0)//当前字符与哈希表里面冲突l=max(l,m[s[r]]);//l移位m[s[r]]=r+1;//哈希表存储下标的后一位ans=max(ans,r-l+1);//求出最大值 } returnans;//输出结果 } };
五、测试结果
从964ms->12ms，不优化了，满足了。
