题干：
难度：Medium
Given a string, find the length of the longest substring without repeating characters.
Example1:
|
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. |
Example2:
|
Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. |
Example3:
|
Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring. |
解析：
学数据结构的时候我就曾被kmp算法困扰过好久，有关字符串的题目显然不要想着用暴力的方法去写，要找到合适的思路来实现。本题需要我们求字符串中最长不重复子串。为了处理子串不重复，建立一个hash表，存放每个字符上次在字符串中出现时的索引值。我的想法是遍历一次字符串便可得到结果，所以我们还需要一个变量pre来存放会使字符串出现重复的最大索引值。例如，对于字符串"fababefgh"，当我们遍历到'g'时，pre为2，因为如果以'g'为末尾字符的子串包含索引为2对应的'b'，就不是不重复的子串，但如果是从索引3或者更大的索引值为首字符，那么这个子串就不含重复字符。
算法开始，初始化hashmap。pre值为-1。对字符串进行遍历，如果当前字符不在hash表中，则存入hash表，并且以pre+1对应的字符为首字符，以此字符为末尾字符的字符串是不重复子串，判断此字符串是否为当前最长的不重复子串。若当前字符已在hash表中，则要判断上一个此字符的索引是否大于pre，若大于pre，则说明从上一此字符到当前的此字符之前的一个字符组成的子串是不重复子串，应当更新pre并判断此字符串是否为当前最长的不重复子串。若小于pre，则以pre+1对应的字符为首字符，以此字符为末尾字符的字符串是不重复子串，判断此字符串是否为当前最长的不重复子串。这样遍历一次即可得到答案。
（汗，自己都感觉自己把算法讲得太抽象了，如果不大理解就对着代码和注释理解一下就好了，关键是要如何简明且不遗漏地寻找、判定所有不重复子串）
Java解法
我的Java代码中利用了HashMap，因为题目针对的是字母空格等ascii表中的字符。所以也可以直接利用int数组，数组索引为字符的ascii码，内容为字符上一次在字符串中出现的索引值，可以达到更快的速度。
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character,Integer> hm=new HashMap<Character,Integer>();
//变量nlen用于记录当前的最长子串长度，pre用来记录当前会产生重复的字符中索引的最大值
int nlen=0;int pre=-1;
//只对字符串做一次遍历
for (int i=0;i<s.length();i++){
//如果hash表中已经有了当前处理的字符，则我们得到了一个子串
if(hm.containsKey(s.charAt(i))){
//对于这个子串，子串中间可能存在字符重复，利用pre进行判断
//子串的首字符索引大于pre，则要更新pre
if(hm.get(s.charAt(i))>pre){
pre=hm.get(s.charAt(i));
//再判断这个子串是否是新的最长不重复子串
if(i-hm.get(s.charAt(i))>nlen){
nlen=i-hm.get(s.charAt(i));
}
}
//子串首字符索引小于pre，则从pre+1对应的字符到这个字符又可以组成一个不重复子串
else{
if(i-pre>nlen){
nlen=i-pre;
}
}
//更新hash表
hm.put(s.charAt(i),i);
}
//hash表中没有当前字符,则从pre+1对应的字符到这个字符又可以组成一个不重复子串
else{
//先这hash表中记录当前字符
hm.put(s.charAt(i),i);
//再判断子串是否是新的最长不重复子串
if(i-pre>nlen){
nlen=i-pre;
}
}
}
return nlen;
}
}Python解法
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
#nelen为当前最长无重复子串长度，pre记录当前会产生重复的字符中索引的最大值
nlen=0;pre=-1;
#用一个字典存放每个字符上次出现的索引值
hm={}
for i in range(len(s)):
#字典中已有当前字符，得到一个子串
if s[i] in hm.keys():
#对于这个子串，子串中间可能存在字符重复，利用pre进行判断
#子串的首字符索引大于pre，则要更新pre
if(hm[s[i]]>pre):
pre=hm[s[i]]
#再判断这个子串是否是新的最长不重复子串
if i-hm[s[i]]>nlen:
nlen=i-hm[s[i]]
#子串首字符索引小于pre，则从pre+1对应的字符到这个字符又可以组成一个不重复子串
else:
if i-pre>nlen:
nlen=i-pre
#更hash表
hm[s[i]]=i
#hash表中没有当前字符,则从pre+1对应的字符到这个字符又可以组成一个不重复子串
else:
#先这hash表中记录当前字符
hm[s[i]]=i
#再判断子串是否是新的最长不重复子串
if i-pre>nlen:
nlen=i-pre
return nlen