转载：http://www.cnblogs.com/haozhengfei/p/d0906ebc98f7b6eaecb3ecd738dc78ac.html
无重复字符的最长子串
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。
分析：
最优解时间复杂度为O(n)，空间复杂度为O(n)
map 统计了每个字符最后一次出现的位置
maxLength 记录当前最长不重复子串长度
currentLength 记录以当前字符 chars[i] 或char[i-1] 结尾的最长不重复子串长度
chars[pre] 表示以 i 结尾的最长不重复子串的第一个字符
情况1：如果c上次出现的位置在chars[pre]之后，则最长不重复子串从c的后一个字符开始到当前c结束
image
情况2：如果c上次出现的位置在chars[pre]之前，则最长不重复子串从chars[pre]开始，到当前c结束
image
情况3：如果c没有出现过，则 currentLength+1
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<Character, Integer>();
char[] chars = s.toCharArray();
int maxLength=0;
int currentLength=0;
int pre;
for(int i=0;i<chars.length;i++){
if(map.containsKey(chars[i])){
pre = i-currentLength;
//情况1
if(pre>map.get(chars[i])){
currentLength++;
}else{
//情况2
currentLength=i-map.get(chars[i]);
}
}else {
//情况3
currentLength++;
}
if(currentLength>maxLength){
maxLength=currentLength;
}
map.put(chars[i],i);
}
return maxLength;
}
