企业官网建设流程全解析

原题链接

思路

分析后发现适合每次选择一个字符加入结果数组，通过双指针从一侧开始，R 指针负责尝试添加入字符，如果当前字符已经存在，那么左移 L 指针直到 R 指针可以加入。
那么分析后就是O(n) 的时间复杂度，符合题意。

代码

需要注意的是这里是字符，而不是数字，所以记录出现字符次数的数字长度应该为128。

classSolution{public:intlengthOfLongestSubstring(string s){intl=0;intn=s.size();intans=0;vector<int>cnt(128,-1);for(inti=0;i<n;i++){while(l<=i&&cnt[s[i]]!=-1){cnt[s[l]]=-1;l++;}cnt[s[i]]=i;ans=max(ans,i-l+1);}returnans;}};

优化

其实这里还可以优化。注意到左指针其实移动目的就是，去除当前数组中包含右指针位置的字符。这里的cnt数组只是为了记录是否存在，那么现在可以用来记录上次这个字符出现的位置，初始化为-1。
那么这里可以加速 L 指针的移动，之前最坏可以到达O(2n)。

classSolution{public:intlengthOfLongestSubstring(string s){intlen=0;intl=0;intn=s.size();intans=0;vector<int>cnt(128,-1);for(inti=0;i<n;i++){if(cnt[s[i]]>=l){l=cnt[s[i]]+1;}cnt[s[i]]=i;ans=max(ans,i-l+1);}returnans;}};

改进后速度从10ms左右降低到4ms ，大概是快一半。

总结

这个题目主要还是使用双指针，观察到结构构造方式后就可以有大致的思路了。
然后就是这里左右指针形成的逻辑区域了，中途对于是左开右闭还是左闭右闭区间考虑了一下，最后还是选择了后者。不过发现最后还是不熟练，还是相对固定的形式。