这种类型题第一次做，还是花了比较长的时间的，一共写了两三个版本才写出比较快的方法 1、最后的方法：44ms左右，使用滑动窗口，创建左右两个“指针”，一个哈希表保存<字母，字母在字符创中的索引>，如果后面发现有重复了，就把重复的字母之前都删除掉，改变这个字母的哈希表的值，改变左指针位置。好的测试案例有：“abcbacbb”，“dvdf”，“”，“vdsdf”
#include <list> #include <algorithm> #include <set> #include <queue> #include <iostream> #include <string> #include <stack> #include <unordered_map> #include <unordered_set> using namespace std; //3. 无重复字符的最长子串 class Solution { public: int lengthOfLongestSubstring(string s) { if (s.size() == 0) { return 0; } unordered_map<char,string::iterator> myHash; string::iterator itLeft = s.begin(); string::iterator itRight = s.begin(); int MaxLength = -1; while (itRight != s.end()) { auto index = myHash.find(*itRight); if (index != myHash.end()) { auto temp_pos = index->second + 1;//临时保存一下以后左指针的位置，防止指针瞎指 for (auto i = itLeft; i < index->second; i++) {//把重复的字母之前的字母删除掉 myHash.erase(*i); } myHash[*itRight] = itRight;//改一下重复字母本身的索引 //重大问题 ，index已经是空指针了，前面保存起来必须 !本质是个指针的！ //itLeft = index->second;这里一定要注意，引以为戒 itLeft = temp_pos;//改左指针指向的位置 } else { myHash[*itRight] = itRight; } MaxLength = max(MaxLength, int(itRight - itLeft+1)); //printf("%d\n", int(itRight - itLeft)); itRight++; } return MaxLength; } }; int main(void) { Solution solution; int res = solution.lengthOfLongestSubstring("abcabcbb"); return 0; }2、第一个想到的方法：找出 从每一个字符开始的，不包含重复字符的最长子串，两次循环，用了1400+ms，太拉胯了
int lengthOfLongestSubstring(string s) { if (s.size() == 0) { return 0; } unordered_set<char> charSet; string::iterator itLeft = s.begin(); int MaxLength = -1; int CurrentLength = 0; while (itLeft != s.end()) { auto itRight = itLeft; while (itRight != s.end()) { if (charSet.count(*itRight)) { //charSet.erase(*itLeft);//左右一样的，不弹也不加 MaxLength = max(MaxLength, CurrentLength); //CurrentLength--; break; } else { charSet.insert(*itRight); CurrentLength++; } itRight++; } charSet.clear(); MaxLength = max(MaxLength, CurrentLength); CurrentLength = 0; itLeft++; } return MaxLength; }学无止境，天道酬勤
