C++寻找无重复字符的最长子串（桶优化解决）（二）

图片: 图片链接: 点击链接.
因为视频图片无法转载&＃xff0c;所以详情就查看上面图片链接。
具体看代码解释&＃xff1a;注意&＃xff1a;桶内值得大小表示了相应字符在字符串中的位置

class Solution
{
public:int lengthOfLongestSubstring(string s){int start(0),end(0),length(0),res(0);//分别定义起始指针&＃xff0c;末尾指针&＃xff0c;非重复子串大小&＃xff0c;最大非重复子串大小int ss&＃61;s.size();vector<int> rec(128,-1);//设定一个桶&＃xff0c;桶的大小刚好放下所有字母&＃xff0c;//字母在桶中的位置对应的ASCII码&＃xff0c;初始值均为-1&＃xff0c;表示位置尚未出现while(end<ss){int asc&＃61;int(s[end]);//将字符转换成相应的ASCII码if(rec[asc]>&＃61;start){//最难得是这三行代码&＃xff1a;start&＃61;rec[asc]&＃43;1; //我们rec中存储的是位置&＃xff0c;那么当读到一个元素在rec中非-1表示他在之前出现过&＃xff0c;length&＃61;end-start;//若是大于start即头字符位置表示他在start后面出现过&＃xff0c;也就是重复了&＃xff0c;//那么头字符串直接移到重复字符串后面一位&＃xff0c;重新确定非重复字符串及其长度}rec[asc]&＃61;end;//在桶中更新尾字符的位置length&＃43;&＃43;;//更新长度end&＃43;&＃43;;//更新尾指针res&＃61;max(length,res);//更新最大长度}return res;}
};


这个写法相当的妙&＃xff0c;且省时间&＃xff0c;原因在于他如果发现了重复的字符串&＃xff0c;则会直接跳到重复字符后面一位进行新的非重复字符串长度确定而不用一位一位遍历确定前面在哪一位重复了