给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
也就是给定一个字符串，然后求出最长的子串长度，子串的要求是不能有重复字符。
评论解一，循环查找字符串，把有的数据放到一个数组中，每次判断设置子串长度，发现要插入的字符已经存在数组中时，表示有重复，然后从开头删除子串，知道要插入的数据无冲突。这个算法很巧妙，速度效率都很好。
评论解二，两个循环，一头一尾，尾部不断向后移动，每次从头部遍历，发现重复字符串，设置头部开始位置到当前重复字符串下一位置，计算子串长度。
我的解一，把每个字符串放到一个map中，key是字符串，value是对应索引位置。一次遍历。发现map中已有，那么就出现了重复，计算当前到子串开始时的长度，然后把子串开始的索引设置为当前输入重复的字符索引加一，把从原始开始索引到当前索引之间的map数据重置。这个与评论解一类似。
class Solution { public: int lengthOfLongestSubstring(string s) { int len = 0; int sindex = 0; int eindex = 0; if (!s.empty()) { unordered_map<char, int> charindexmap; while (eindex < s.size()) { if (sindex == eindex) { len = 1; } else { if (charindexmap.count(s[eindex]) > 0 && charindexmap[s[eindex]] > -1) { if (len < eindex - sindex) { len = eindex - sindex; } int i = sindex; sindex = charindexmap[s[eindex]] + 1; for (; i < sindex; i++) { charindexmap[s[i]] = -1; } if (sindex > eindex) { sindex = eindex; } } } charindexmap[s[eindex]] = eindex; eindex++; } } if (len < eindex - sindex) { len = eindex - sindex; } return len; } };
坑一，没有重置从开始索引到重复字符串之间的数据，导致结果不正确
坑二，空字符串，执行错误
坑三，直接使用map，导致初始化了数据，计算错误
坑四，把map记录使用混淆
我的解二，map可以之后，就可以考虑改成数组，效率和空间都有提升
class Solution { public: int lengthOfLongestSubstring(string s) { int len = 0; int sindex = 0; int eindex = 0; if (!s.empty()) { int charindexmap[256] = { 0 }; memset(charindexmap, -1, 256 * sizeof(int)); while (eindex < s.size()) { if (sindex == eindex) { len = 1; } else { if (charindexmap[s[eindex]] > -1) { if (len < eindex - sindex) { len = eindex - sindex; } int i = sindex; sindex = charindexmap[s[eindex]] + 1; for (; i < sindex; i++) { charindexmap[s[i]] = -1; } if (sindex > eindex) { sindex = eindex; } } } charindexmap[s[eindex]] = eindex; eindex++; } } if (len < eindex - sindex) { len = eindex - sindex; } return len; } };
数组的坑又多了几个
坑一，初始化使用错误
坑二，数组map用了char类型，导致超过256长度的字符串越界，改成了int，理论也会越界。不过足够了
原文：https://www.cnblogs.com/studywithallofyou/p/11984552.html