Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
这道求最长无重复子串的题和之前那道 Isomorphic Strings 同构字符串很类似，我们还是建立一个256位大小的整型数组来代替哈希表，这样做的原因是ASCII表共能表示256个字符，所以可以记录所有字符，然后我们需要定义两个变量res和left，其中res用来记录最长无重复子串的长度，left指向该无重复子串左边的起始位置，然后我们遍历整个字符串，对于每一个遍历到的字符，如果哈希表中该字符串对应的值为0，说明没有遇到过该字符，则此时计算最长无重复子串，i - left +１，其中ｉ是最长无重复子串最右边的位置，left是最左边的位置，还有一种情况也需要计算最长无重复子串，就是当哈希表中的值小于left，这是由于此时出现过重复的字符，left的位置更新了，如果又遇到了新的字符，就要重新计算最长无重复子串。最后每次都要在哈希表中将当前字符对应的值赋值为i+1。代码如下：
C++ 解法一：
class Solution { public: int lengthOfLongestSubstring(string s) { int m[256] = {0}, res = 0, left = 0; for (int i = 0; i < s.size(); ++i) { if (m[s[i]] == 0 || m[s[i]] < left) { res = max(res, i - left + 1); } else { left = m[s[i]]; } m[s[i]] = i + 1; } return res; } };
这里解释下程序中那个if条件语句中为啥要有个m[s[i]] < left，我们用一个例子来说明，当输入字符串为"abbca"的时候，当i=4时，也就是即将要开始遍历最后一个字母a时，此时哈希表表中a对应1，b对应3，c对应4，left为2，即当前最长的子字符串的左边界为第二个b的位置，而第一个a已经不在当前最长的字符串的范围内了，那么对于i=4这个新进来的a，应该要加入结果中，而此时未被更新的哈希表中a为1，不是0，如果不判断它和left的关系的话，就无法更新结果，那么答案就会少一位，所以需要加m[s[i]] < left。
下面这种写法是上面解法的精简模式，思路都一样：
C++ 解法二：
class Solution { public: int lengthOfLongestSubstring(string s) { vector<int> m(256, -1); int res = 0, left = -1; for (int i = 0; i < s.size(); ++i) { left = max(left, m[s[i]]); m[s[i]] = i; res = max(res, i - left); } return res; } };
Java 解法二：
public class Solution { public int lengthOfLongestSubstring(String s) { int[] m = new int[256]; Arrays.fill(m, -1); int res = 0, left = -1; for (int i = 0; i < s.length(); ++i) { left = Math.max(left, m[s.charAt(i)]); m[s.charAt(i)] = i; res = Math.max(res, i - left); } return res; } }
下面这种解法使用了set，核心算法和上面的很类似，把出现过的字符都放入set中，遇到set中没有的字符就加入set中并更新结果res，如果遇到重复的，则从左边开始删字符，直到删到重复的字符停止：
C++ 解法三：
class Solution { public: int lengthOfLongestSubstring(string s) { set<char> t; int res = 0, left = 0, right = 0; while (right < s.size()) { if (t.find(s[right]) == t.end()) { t.insert(s[right++]); res = max(res, (int)t.size()); } else { t.erase(s[left++]); } } return res; } };
Java 解法三：
public class Solution { public int lengthOfLongestSubstring(String s) { int res = 0, left = 0, right = 0; HashSet<Character> t = new HashSet<Character>(); while (right < s.length()) { if (!t.contains(s.charAt(right))) { t.add(s.charAt(right++)); res = Math.max(res, t.size()); } else { t.remove(s.charAt(left++)); } } return res; } }
本文转自博客园Grandyang的博客，原文链接：最长无重复子串[LeetCode] Longest Substring Without Repeating Characters ，如需转载请自行联系原博主。
