在拿到这个题目我第一时间想的是用map统计字符串中字符出现的情况，然后记录最长子串写出程序如下：
static const auto io_speed_up = []() { std::ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }(); class Solution { public: int lengthOfLongestSubstring(string s) { char c; int begin = 0; int maxLength = 0; int nowLength = 0; size_t length = s.length(); unordered_map<char, int> strMap{ {‘a‘, -1}, {‘b‘, -1}, {‘c‘, -1}, {‘d‘, -1}, {‘e‘, -1}, {‘f‘, -1}, {‘g‘, -1}, {‘h‘, -1}, {‘i‘, -1}, {‘j‘, -1}, {‘k‘, -1}, {‘l‘, -1}, {‘m‘, -1}, {‘n‘, -1}, {‘o‘, -1}, {‘p‘, -1}, {‘q‘, -1}, {‘r‘, -1}, {‘s‘, -1}, {‘t‘, -1}, {‘u‘, -1}, {‘v‘, -1}, {‘w‘, -1}, {‘x‘, -1}, {‘y‘, -1}, {‘z‘, -1} }; for (size_t i = 0; i < length; ++i) { c = s.at(i); if (strMap[c] == -1) { ++nowLength; strMap[c] = i; } else { maxLength = maxLength > nowLength ? maxLength : nowLength; nowLength -= (strMap[c] - begin); while (begin <= strMap[c]) { strMap[s.at(begin)] = -1; ++begin; } strMap[c] = i; } } return maxLength > nowLength ? maxLength : nowLength; } };
但是提交之后发现只快于65.17%的程序，就去看了一下最优解，最优解代码如下：
static const auto io_speed_up = []() { std::ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }(); class Solution { public: int lengthOfLongestSubstring(string s) { int size = s.size(); vector<int> dict(256,-1); int maxlen = 0; int start = -1; for (int i=0;i<size;i++) { if (dict[s[i]] > start) { start = dict[s[i]]; } dict[s[i]] = i; maxlen = max(maxlen, i - start); } return maxlen; } };
二者思路相似都是通过对应字符串中的字符出现，当出现重复字符时，抛弃重复出现的字符前一次出现的位置，把新的子串开始位置设置为其+1来统计子串长度，最后得出最长的子串长度。执行速度区别我认为出现在以下两个方面：
一是开辟了一个长度为256（char型最多为256）的vector数组来比较字符，这样可以充分得利用数据的局部性，加快内存读取速度。
二是他的比较方式是比较新出现的字符是否比上个字符出现的位置更远，之后直接替换。而我是比较字符对应的出现节点是否是初始化为-1的如果是，那么替换，这样我在出现重复字符的时候就要对前面的字符串进行重置，这里多了循环次数。
有时候不得不承认，别人写的程序比你短，比你容易理解，执行效率还比你高。sad。
原文：https://www.cnblogs.com/change4587/p/9146615.html